QuickSort – Understanding the QuickSort Algorithm and Implementation6 min read


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]

10987654321

First Iteration…

Start Index = 0, End Index = 10

i=0; j=0;
10987654321

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
10987654321

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
10187654329

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
10187654329

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
10187654329

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
11087654329

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
18107654329

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
18710654329

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
18761054329

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 one
Increment j by 1

new value of i is 5 and j is 6

i=5;j=6;pivot
18765104329

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
18765410329

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
18765431029

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
18765432109

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
18765432910

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.


  • Article By: Varun Shrivastava

  • Varun Shrivastava is an innovative Full Stack Developer at ThoughtWorks with around 4 years of experience in building enterprise software systems in finance and retail domain. Experienced in design, development, and deployment of scalable software. He is a passionate blogger and loves to write about philosophy, programming, tech and relationships. This is his space, you can get in touch with him here anytime you want.