QuickSort algorithm is a brilliant idea of Tony Hoare. This algorithm is so effective that if implemented well, it can be 2x or 3x faster than its competitors merge sort and heap sort.
I personally like quick sort algorithm because of its simplicity and speed. But I’m surprised to see that so many people get confused with quick sort algorithm.
But worry not, because I think I know the reason now 🙂
The reason people are scared of the QuickSort algorithm is that it involves recursion. And I totally agree, recursion is a bit difficult to grasp at first, especially if you are just starting off with the algorithms.
In this article, I’ve made an effort to explain the QuickSort algorithm in the easiest way I could.
Actually the way I’m going to explain to you is the way I’ve understood it. And trust me, once you understand the concept, coding becomes easy and once you are comfortable with the code then you can play around with it in your style.
If you are interested in programming then do visit bemyaficionado.com/programming to find more such articles.
QuickSort Single Iteration
Let’s take it real slow and see what happens in the very first iteration.
I’ve tried my best to generate the below HTML using print statements in the quicksort program. Just give it some time and carefully visit every step and try to understand what’s happening. This is the only way to learn (look under the hood).
And the first iteration is the crux of it all. If you understand the first iteration, you understand the quicksort. Okay, here it is…
Input Array = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
| 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
First Iteration…
Start Index = 0, End Index = 10
| i=0; j=0; | |||||||||
| 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
Let’s select a random index from the array and name it as the pivot.
Let’s say we select index = 1 as pivot
Pivot Index = 1
Value at Pivot Index = 9
| i=0; j=0; | pivot | ||||||||
| 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
Let’s put the selected pivot at the end of the array.
So the array now becomes this, Array = [10, 1, 8, 7, 6, 5, 4, 3, 2, 9]
| pivot | |||||||||
| 10 | 1 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 9 |
So far so good… we haven’t begun with the iteration yet.
Now, let’s take two variables (say, i & j) and assign the starting index to them such that the value of i=0 and j=0
| i=0; j=0; | pivot | ||||||||
| 10 | 1 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 9 |
Now, let’s start the iteration.
Iterate until j=0 reaches the last index (i.e 9)
In the while loop, we will compare the value of arr[j] with the selected pivot value (9).
Let’s see how the value of j and i changes over the iteration.
i=0, j=0
Increment j by 1
new value of i is 0 and j is 1
i=0, j=1
| i=0; | j=1; | pivot | |||||||
| 10 | 1 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 9 |
value at j=1 is (1) is smaller than the pivot (9)
so we swap the values at index 0 with 1 and increment i by one
Increment j by 1
new value of i is 1 and j is 2
| i=1; | j=2; | pivot | |||||||
| 1 | 10 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 9 |
i=1, j=2
value at j=2 (8) is smaller than the pivot(9)
so we swap the values at index 1 with 2 and increment i by one
Increment j by 1
new value of i is 2 and j is 3
| i=2; | j=3; | pivot | |||||||
| 1 | 8 | 10 | 7 | 6 | 5 | 4 | 3 | 2 | 9 |
i=2, j=3
value at j=3 (7) is smaller than the pivot(9)
so we swap the values at index 2 with 3 and increment i by one
Increment j by 1
new value of i is 3 and j is 4
i=3, j=4
| i=3; | j=4; | pivot | |||||||
| 1 | 8 | 7 | 10 | 6 | 5 | 4 | 3 | 2 | 9 |
value at j=4 (6) is smaller than the pivot(9) so we swap the values at index 3 with 4 and increment i by one
Increment j by 1
new value of i is 4 and j is 5
| i=4; | j=5; | pivot | |||||||
| 1 | 8 | 7 | 6 | 10 | 5 | 4 | 3 | 2 | 9 |
i=4, j=5
value at j=5 (5) is smaller than the pivot(9)
so we swap the values at index 4 with 5 and increment i by oneIncrement j by 1
new value of i is 5 and j is 6
| i=5; | j=6; | pivot | |||||||
| 1 | 8 | 7 | 6 | 5 | 10 | 4 | 3 | 2 | 9 |
i=5, j=6
value at j=6 (4) is smaller than the pivot(9) so we swap the values at index 5 with 6and increment i by one
Increment j by 1
new value of i is 6 and j is 7
| i=6; | j=7; | pivot | |||||||
| 1 | 8 | 7 | 6 | 5 | 4 | 10 | 3 | 2 | 9 |
i=6, j=7
value at j=7 (3) is smaller than the pivot(9) so we swap the values at index 6 with 7 and increment i by one
Increment j by 1
new value of i is 7 and j is 8
| i=7; | j=8; | pivot | |||||||
| 1 | 8 | 7 | 6 | 5 | 4 | 3 | 10 | 2 | 9 |
i=7, j=8
value at j=8 (2) is smaller than the pivot(9) so we swap the values at index 7 with 8 and increment i by one
Increment j by 1
the new value of i is 8 and j is 9
| i=7; | j=8; | pivot | |||||||
| 1 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 10 | 9 |
Finally j has reached the pivot, which means i is the correct index for the pivot.
So let’s swap them.
Now the pivot has reached its correct position that is at index 8 when the array is sorted in the ascending order.
| i=7; | j=8; | pivot | |||||||
| 1 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 9 | 10 |
In the first iteration, the pivot number 9 has reached its correct position in the array (if sorted ascending). Similarly, every iteration we pick one pivot and make sure it reaches its correct position.
Another way to look at this is that after the end of the iteration all the numbers that are smaller than the pivot are moved to its left and all the numbers greater than the pivot has moved to its right.
If we perform the same steps over and over again with different pivots, at the end we will have the sorted array. So, the best-case scenario would be O(nlogn). But the worst case could still be O(n2).
The worst case is very unlikely. For the worst case, you would have to be really unlucky to pick the bad pivot every time. And by bad I mean either you pick the pivot from the start or end.
Complete QuickSort Algorithm
Now that we have seen the first iteration, we just have to do it for all the numbers in the array.
The best way to do it for all the numbers is to recursively sort the left side of the array and the right side of the array.
So, in the above example, break the array into two logical parts e.g. index 0-7 and 9. Since the right array contains only one element which means it is already sorted. So, you will sort the left array and so on recursively.
Here’s the entire code for the same.
Conclusion
Now that you have understood how it works, analyze the above code, put print statements here and there and fit it in your brain. This algorithm is not just helpful in sorting the array but also very useful for solving nth order statistics.
Maybe in the next article, I will give you a glimpse of nth order statistics problem.
Let me know if you are facing any problem understanding the code. Comment below… that’s the fastest way to get an answer.