Quicksort is a popular sorting algorithm with O(nlogn) best and average-case performance, and O(n2) worst case performance when sorting n elements.
- If the list only has a single element return it.
- Pick a pivot.
- Move elements around until bigger elements are to the right and smaller elements are to the left of the pivot.
- Recursively apply the above steps to the left and right groups of elements.
Here are a few test cases to check that our implementation does what it’s supposed to do:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
And then the implementation:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
Given the following array:
The first step is to pick a pivot. The choice of a pivot can significantly improve the performance of Quicksort. For this implementation we will use a random element in the array as a pivot. One alternative would be to use the ‘Median-of-three’ as suggested by Robert Sedgewick (pick the first, middle and last elements of the array and use their median as a pivot).
Say the result of the above operation is
pivot_index = 0. The next step is
to call the partition function, which will move all elements less than 2 to the left and all elements
greater than 2 to the right of the pivot and return the new position of the
We need to track the position of the new pivot index, so we start off by setting it to the left-most element. Next we move the pivot out of the way by swapping it with the right-most element, resulting in the following changes:
Now we loop through all the elements excluding the pivot — left to right — comparing them with the pivot. If an element is less than or equal to the pivot, we swap that element with the element at the position of the new pivot index and increment the new pivot index by 1.
The first two elements, 5 and 3, are less than 2 so no operations are performed. On the third comparison, we swap 1 and 5 and increment the new pivot index by 1 resulting in the following changes:
The loop is complete so the next step is to swap the pivot with the element at the new pivot index resulting in the following changes:
We return the new pivot index to the calling function as now we have successfully partitioned the array around the pivot, 2.
Next we call sort! recursively on the elements to the left of 2. However since that’s an array with a single element, 1, that recursive fork ends with no additional operations.
For the elements to the right of we follow the same steps as above:
- Pick a pivot: (a random element in our array:
- Say we picked 3, call partition on the array, starting with the following configuration:
- Since the pivot is the right-most element, we don’t need to move it out of the way.
- First and only comparison: 5 is greater than the pivot so no operations performed.
- Loop exits, now we swap the pivot with the element at the new pivot index resulting in the following changes:
The array is successfully partitioned and we return the new pivot index to the calling function.
Continuing with the recursion, we call sort! recursively on elements to the left and right of the pivot, 3. But since there are no elements to the left of, and a single element to the right of the pivot, the right fork of the main recursive fork is done.
Finally we return the array, which is completely sorted at this point!
You can find the complete code on github