Quick Sort Algorithm - The Coding Shala
In this post, we will learn what is Quick Sort Algorithm and will write a Java program for Quick Sort.
Quick Sort Algorithm
Working of Quick Sort Algorithm
- step 1. First, we select a value from the list, called pivot value and it divides the list into two sublists. One sublist contains all the values that are less than the pivot value, another sublist contains the values that are greater than or equal to the pivot value. This process is also called partitioning. we can choose the first/last element in the list as the pivot or can randomly pick an element from the list.
- Step 2. We repeat this partitioning process to reduce the list into two smaller sublists. We then recursively sort the two sublists.
- Step 3. After the partitioning process, we can simply concatenate the two sorted sublists.
Time Complexity of Quick Sort Algorithm
The time complexity of quick sort depends on the pivot value and it varies from O(N log N) in the best case and O(N^2) in the worst case.
Quick Sort Algorithm Java Program
- Merge Sort Algorithm
- Insertion Sort Algorithm
- Counting Sort Algorithm
- Bucket Sort Algorithm
- Sliding Window Algorithm