Finally we arrive at learning about a fast algorithm that will actually solve us the problem very quickly.
This article is a continuation on the insertion sort article. If you didn’t read it, you can do so by clicking here.
This algorithm is much more complicated than the previous ones and there are many ways to implement it to achieve better performance depending on the sorting problem we’re trying to solve. We will learn a version of the algorithm that is totally acceptable for a general purpose scenario like ours.
One of the biggest differences of this algorithm compared to the previous ones is that it shifts elements around much faster. Instead of just going from left to right to compare the elements or find the minimum, quick sort goes from left to right and right to left “at the same time”. Another thing that makes this algorithm much more different is the fact that it’s recursive.
fun <T : Comparable<T>> DynamicArray<out T>.quickSort() {
quicksort(this, 0, size() - 1)
}Our quick sort will be defined by that, notice that we invoke another quick sort function with two numbers, in this case the initial index where we will begin sorting and the last index. This function is defined like this:
fun <T : Comparable<T>> quicksort(
array: DynamicArray<out T>, lo: Int, hi: Int
) {
if (lo < hi) {
val p = partition(array, lo, hi)
quicksort(array, lo, p)
quicksort(array, p + 1, hi)
}
}Basically that’s it, we partition the array in two parts and apply the same function to the left part and the right part.
The magic is both in the beauty of the recursion and in the partition function. In our case the partition function will be defined like this:
fun <T : Comparable<T>> partition(
array: DynamicArray<out T>, lo: Int, hi: Int
): Int {
val pivot: T = array[(hi + lo) / 2]
var i = lo - 1
var j = hi + 1
while (true) {
do {
i++
} while (array[i] < pivot)
do {
j--
} while (array[j] > pivot)
if (i >= j) return j
swap(array, i, j)
}
}The pivot
A very important concept in quick sort is the concept of pivot!
It could be any element but for our purposes we will use the middle one. Choosing the best pivot is out of the scope of this article. Using the middle one is very good to illustrate the algorithm.
How it works
We start with the array [7, 5, 2, 4, 1, 3, 6].
Our pivot will be 4 in this case.
We will go from left to right and from right to left to put all the elements that are smaller than the pivot to the left side of the pivot and all the elements that are larger will be put to the right side of the pivot.
7 is bigger than the pivot so it has to be changed to the right side.
We will find a spot for it on the right side.
6 is bigger than the pivot so it’s correct
3 is smaller than the pivot so we can swap 7 and 3.
We now have this: [3, 5, 2, 4, 1, 7, 6]
5 is bigger than the pivot so we will find a spot for it.
1 is small than the pivot so we swap 5 and 1 and get this:
[3, 1, 2, 4, 5, 7, 6]
2 is smaller than the pivot so we’re finished. Now we have to apply quick sort to both halves [3, 1, 2] and [5, 7, 6]
1 is the pivot now. 3 is not correct because it’s bigger than the pivot, 2 is correct so we swap and get [1, 3, 2]. We have to split again and you see where this is going.
After the left part is done we do the same on the right side.
It’s much easier to see an example in video but hopefully you can understand the idea.
Performance
On my machine it took 414ms to sort the array. Yes, it’s real. We dropped the sorting time from 22 minutes to 414 milliseconds.
Can it be faster?
If we look at the way we’re trying to solve this problem we might see that there is something that we’re caring about that we might not need.
All these articles about the sorting algorithms were necessary because we started with the desire to perform a binary search!
Sometimes it can happen that you focus on a particular way of solving a problem and you try to optimize it when your initial solution was probably not the best one in the first place.
We’re using a list of words and one property of a list is that the elements have a certain order, they can be accessed by an index. There is this notion of word on position zero, position one, etc.
But why are we using a list in the first place? What we actually want is to use a set, not a list. We don’t care about accessing the words directly, we just need to know if they exist or not.
We would like to have an interface like this:
interface Set<T> {
fun add(e: T)
fun contains(e: T): Boolean
}Of course we could just make our linked list and dynamic array implement the Set interface but there is a better way. There is a data structure called a binary tree that might help us to solve this problem in a much better way.
But that’s a topic for another article. Stay tuned!