Quick sort is a widely used sorting algorithm developed by C. A. R. Hoare that makes O(n log n) comparisons in the average case to sort an array of n elements. However, in the worst case, it has a quadratic running time given as O(n²) . Basically, the quick sort algorithm is faster than other O(n log n) algorithms, because its efficient implementation can minimize the probability of requiring quadratic time. Quick sort is also known as partition exchange sort.
Quick sort uses Divide and Conquer strategy to sort an array.
- Divide a large list/array into a number of smaller lists/arrays.
- Sort them separately.
- Combine the results to get the sorted list.
Divide and Conquer Technique
- Select an element pivot from the array elements.
- Rearrange the elements in the array in such a way that all elements that are less than the pivot appear before the pivot and all elements greater than the pivot element come after it (equal values can go either way). After such a partitioning, the pivot is placed in its final position. This is called the partition operation.
- Recursively sort the two sub-arrays thus obtained. (One with sub-list of values smaller than that of the pivot element and the other having higher value elements.)
Like merge sort, the base case of the recursion occurs when the array has zero or one element because in that case the array is already sorted. After each iteration, one element (pivot) is always in its final position. Hence, with every iteration, there is one less element to be sorted in the array.
Thus, the main task is to find the pivot element, which will partition the array into two halves. To understand how we find the pivot element, follow the steps given below. (We take the first element in the array as pivot.)
- Set the index of the first element in the array to loc and left variables. Also, set the index of the last element of the array to the right variable.
That is, loc = 0 , left = 0 , and right = n–1 (where n in the number of elements in the array)
- Start from the element pointed by right and scan the array from right to left, comparing each element on the way with the element pointed by the variable loc .
That is, a[loc] should be less than a[right] .
(a) If that is the case, then simply continue comparing until right becomes equal to loc . Once right = loc , it means the pivot has been placed in its correct position.
(b) However, if at any point, we have a[loc] > a[right] , then interchange the two values and jump to Step 3.
(c) Set loc = right
- Start from the element pointed by left and scan the array from left to right, comparing each element on the way with the element pointed by loc .
That is, a[loc] should be greater than a[left] .
(a) If that is the case, then simply continue comparing until left becomes equal to loc . Once left = loc , it means the pivot has been placed in its correct position.
(b) However, if at any point, we have a[loc] < a[left] , then interchange the two values and jump to Step 2.
(c) Set loc = left .
Sort the elements given in the following array using quick sort algorithm.
Quick Sort Example
Now left = loc, so the procedure terminates, as the pivot element (the first element of the array, that is, 27) is placed in its correct position. All the elements smaller than 27 are placed before it and those greater than 27 are placed after it.
The left sub-array containing 25, 10, 18 and the right sub-array containing 36 and 45 are sorted in the same manner.
Quick sort partitions (uses partition function) an array and then calls itself recursively to sort the two resulting subarrays.
Quick Sort Algorithm
Time Complexity of Quick Sort Algorithm
Quick sort is too much efficient for large sized array as its best case and average case complexity is O(n logn), while its worst case complexity is O(n²), where n is the number of elements in an array.
C Program to implement Quick Sort Algorithm