In a previous blog post, I went over how to implement a merge sort in Ruby. We’re just going to keep the merge train rolling. Next stop: Quicksort! Like merge sort, quicksort is recursive and uses divide & conquer. Its worst case run time is O(n^2), which is on par with selection and insertion sort, but its average is O(n log n), like merge sort. Though the average run time is equal to merge sort, the hidden factor is actually better, so in most cases quick sort will perform better than merge sort in practice.
The big difference in how merge and quick sort operate is that quick sort actually sorts during the divide phase. The sort works by selecting a pivot point and then moving the other elements so that all element less than or equal to the pivot are to its left, and all larger elements are to its right in the array. This movement is called partitioning. Usually the pivot point is the right-most element in the array or subarray. The order of the elements to either side does not matter as we are going to hit them with recursion eventually. The base case will simply be arrays with less than 2 elements, i.e.– nothing to sort.
Once the partitioning is complete we just have to combine the subarrays. They will already be in order! Here is a visual:
OK. let’s start coding. In Ruby. Let’s work on our partition method first; that’s where the real work is. The method is going to take in an array, a “left” value and a “right” value. Those latter 2 values correspond to the left-most and right-most elements in the array. We will go ahead and use the right-most value as the pivot. Then we will go through the other elements in the array left to right, and compare them to the value of the pivot, and then swap indices around to reflect the relative values of the elements. The running time of the partition is O(n).
That is really all the hard work. In order to complete our quick sort, we just need to call it recursively on the original array and return the sorted array. We are going to check the base case, which is just confirming that the original array has more than one element. The complete sort could look something like this.
And that is the quick sort. Again the worst case is worse than merge sort, so it might seem like that’s a better call, but on average quick sort will actually run a little better than merge sort in practice. Enjoy!