Jun 14, 2021
Implementing Quick Select in Ruby
In this blog, we’ll walk through how to write the Quick Select algorithm in Ruby. This technique is used to find the kth smallest element in an unsorted array, with an average runtime complexity of O(n). Quick Select uses a similar approach to the popular Quick Sort algorithm. It is a divide and conquer approach where the array to search is cut into smaller and smaller pieces until the desired result is found.
At first glance, finding the kth smallest element of an array is simple. Just sort the array and pick the element at the index [k - 1]. However, if we do it like this, we will only be as fast as our sorting method, which in most cases is slower than O(n). Using Quick Select thus will ensure we are the most efficient we can be when solving the problem.
The first thing to do is write a partition method. This method has only one purpose: to return the index of a sorted element in an array. We pass in an array along with the section of it to look at via a low and high index.
This method goes through the selected section of the array and swaps the elements based on their relationship to our chosen pivot element, in this case we chose the element corresponding to the high index. A fantastic explanation of this process can be found here.
Now that we have our partition algorithm to find sorted indexes of an unsorted array, we need to write a method to find our element in question!
The arguments passed in to this method are the array in question, the left index, the right index, and of course k which tells us to return the kth smallest element of the array. When we first call this method, the left and right indexes will be 0 and the length of the array minus 1, respectively. As the method recursively calls itself, the distance between left and right will shrink by half each time.
Here are the steps:
- Find a sorted index with the partition method
- Check if that index is the kth smallest element (array[k - 1]), if so, return that element
- If that index is smaller than k -1, search the right half of the array
- If that index is larger than k -1, search the left half of the array
And there we are, by the end we will have found the element we are looking for.
I like this algorithm because it is sneaky in the fact that we don’t need to sort the array. All we need to do is keep finding the index of certain elements in their proper sorted position and we will eventually achieve our goal. This makes Quick Select an awesome choice to search for a particular element.
