Quick Sort

Quick Sort is the algorithm which takes arrays like this:

And sort it to like this

Principle of Quick Sort

• Pick a Pivot Element
• Partitioning Array into three 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.