The quick sort algorithm works as follows:
- 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.)
Quick sort uses partition function to divide an array into two subarrays.
C Program to implement Quick Sort Algorithm.
Output of Quick Sort
- 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 .
Example: 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.