• Skip to main content
  • Skip to primary sidebar
  • Home
  • About
  • Subscribe BMA
  • Contact Us!

Be My Aficionado

Inspire Affection

You are here: Home / Programming / QuickSort – Understanding the QuickSort Algorithm and Implementation

QuickSort – Understanding the QuickSort Algorithm and Implementation6 min read

August 21, 2020 by Varun Shrivastava 1 Comment

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 one
Increment 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.

Share this:

  • Click to share on Facebook (Opens in new window)
  • Click to share on LinkedIn (Opens in new window)
  • Click to share on Twitter (Opens in new window)
  • Click to share on Pinterest (Opens in new window)
  • Click to share on Reddit (Opens in new window)
  • More
  • Click to print (Opens in new window)
  • Click to share on Tumblr (Opens in new window)
  • Click to share on Pocket (Opens in new window)
  • Click to share on Telegram (Opens in new window)
  • Click to share on WhatsApp (Opens in new window)
  • Click to share on Skype (Opens in new window)
  • Click to email this to a friend (Opens in new window)

Filed Under: Programming Tagged With: algorithms, elementary sorting algorithms, implementation, quick sort, quick sort implementation

Reader Interactions

Trackbacks

  1. Prod Deployment - Day In Life Of A Developer - says:
    August 23, 2020 at 5:11 pm

    […] It was 8 AM when I opened my laptop and wrote an article on QuickSort. […]

    Reply

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Primary Sidebar

Featured Posts

Best 5 Useful Advice Every New Blogger must Implement

September 6, 2017 By Varun Shrivastava 1 Comment

Why Pune city is not a good place to Live

March 11, 2017 By Varun Shrivastava 3 Comments

Campus preparation II- How to Clear Group Discussion Rounds

October 9, 2016 By Priyanka Yadav Leave a Comment

Programming Best Practices: The Art of Building Modular Applications

September 15, 2018 By Varun Shrivastava Leave a Comment

Time – Currency of The New Rich

March 5, 2017 By Varun Shrivastava Leave a Comment

Latest Posts

  • Study Abroad Destinations : Research and Review
  • Advent Of Code 2020 – Day 7 – Handy Haversacks
  • Advent Of Code 2020 – Day 6 – Custom Customs
  • Advent Of Code 2020 – Day 5 – Binary Boarding
  • Advent Of Code 2020 – Day 4 – Passport Processing

Categories

  • Blogging (101)
  • Cooking (11)
  • Fashion (7)
  • Finance & Money (12)
  • Programming (50)
  • Reviews (2)
  • Technology (22)
  • Travelling (4)
  • Tutorials (12)
  • Web Hosting (8)
  • Wordpress N SEO (19)

Follow us on facebook

Follow us on facebook

Grab the Deal Now!

Hostgator Starting @$3.95/mo

DigitalOcean Free Credits

Trending

Affordable Hosting amazon aoc-2020 bad luck believe in yourself best database earn money blogging education experience fashion finance Financial Freedom food friends goals google india indian cuisine indian education system java javascript life life changing love make money microservices motivation oops poor education system principles of microservices problem-solving programmer programming reality search engines seo SSD Hosting success technology tips top 5 web web developer wordpress

Copyright © 2021 · BeMyAficionado by Varun Shrivastava · WordPress

loading Cancel
Post was not sent - check your email addresses!
Email check failed, please try again
Sorry, your blog cannot share posts by email.