Thursday, November 8, 2012: Understanding Quicksort (with interactive demo)

At the college, we’re learning about abstract data types and few sorting algorithms, and so in this article I try to explain about the quicksort algorithm using some kind of an interactive demo.

Quicksort is a sorting algorithm, which takes an array like this:

and turns it into this:

This blog post will just explain the concepts of quicksort in a very high level.

I won’t go down into the code, or the analysis of running time, because that’s boring.

Overview of Quicksort

Now, the principle of the quicksort algorithm is this:

• Pick a “pivot” element.
• “Partition” the array into 3 parts:
  • First part: all elements in this part is less than the pivot.
  • Second part: the pivot itself (only one element!)
  • Third part: all elements in this part is greater than or equal to the pivot.
• Then, apply the quicksort algorithm to the first and the third part. (recursively)

Partitioning

An important part of this algorithm is the partitioning — how it partitions an array into 3 parts in-place, that is, without creating extra arrays (like in mergesort). You can do it with some clever algorithm.

Here is one algorithm to partition the array, which I try to present in a way that’s as easy to understand as possible. We’ll try to partition the array like a card game.

• First, assume that the pivot is the leftmost element.
• Flip all the other cards down.
• Then, open each card from left to right.
  • If you find a card that is less than the pivot:
    • Swap that card with the card that was first opened (the leftmost open card), and close that leftmost card.
    • Also take note of the last closed card.
  • Otherwise, continue opening the next card.
• Swap the last closed card with the pivot (if any).
• Open all cards… You will see that the array is already partitioned!

Picking the Pivot

For simplicity, we picked the leftmost element as the pivot, but this isn’t always good. Let’s consider this case where the array is reverse-sorted:

As you can see, the size of the problem is only reduced by 1 in each recursive call.

Note that the steps it take to partition is proportional to the number of elements to partition, therefore the more we can reduce the problem size, the lesser the number of steps.

The best pivot would split the array into 2 equal parts, so the problem size would be reduced by half. That is, the best pivot would be the median of the elements, but to find the median you first need to sort the array (which is what we’re doing), so that wouldn’t work*.

---

One approach that some people use is: just pick a random pivot!

… “but the partitioning algorithm assumes that the pivot is at the leftmost element!”

Easy, just swap the pivot we picked with the leftmost element, then the leftmost element becomes the pivot.

---

Here’s what happens if we were able to choose the best pivot.

---

* I remembered that one friend asked me when he tries to implement the heapsort, the conversation goes like this:

” Do I need to sort the array first? “

” Wait wait wait, what are you trying to implement? “

” Heapsort. “

” Then what’s the point of doing the heap sort if we have to sort the array before we can sort the array using heapsort?! “