Quicksort

Bart Massey

Divide-and-Conquer

• Already seen with Mergesort

• Idea: Break problem up into smaller subproblems, solve the subproblems, combine the solutions to solve the larger problem; solve small-enough problems directly

• Inherently recursive: works when subproblems are always ultimately divisible into base cases, recombinable into solution

• Efficient when splitting and combining are efficient, for example O(n) for Mergesort

Quicksort: Divide-and-Conquer for Arrays

• Idea: Instead of splitting arbitrarily, split the array so that everything in the first part is smaller than everything in the second part

• This allows replacing the merge with just concatenation — but splitting followed by concatenation is identity, so arrays!

• Trick is to partition the array evenly into small and large elements in O(n) time

Partitioning: Pick a Pivot and Proceed

• Imagine we knew the median value of the array; we could then place that value at the front of the array (by swapping it with the first element) and proceed using the following partitioning algorithm (Hoare Partitioning, Wikipedia)

ALGORITHM HOARE PARTITION

To partition an array a:
    i ← 0
    j ← |a|
    p ← a[j]
    loop
      do
        i ← i + 1
      while a[i] < p

      do
        j ← j - 1
      while a[j] > p

      if i ≥ j
        return j

      a[i] ↔ a[j]

Using Partition To Sort (quick)

Now we have a linear-time partition algorithm, so we can just use divide-and-conquer recursion to derive Quicksort

ALGORITHM QUICKSORT

quicksort(a):
    if |a| ≤ 1
      return
    m ← partition(a)
    quicksort(a[1..m])
    quicksort(a[m+1..])

Worst-case Complexity Of Quicksort

• It is tempting to apply the Master Theorem here and conclude n lg n

• Sadly, the partition algorithm in no way guarantees an even split

• Consider a sorted array of integers… Now you are O(n²)

Average-case Complexity Of Quicksort

• Strangely, the average case isn't too bad here: on average the pivot of a random array will be near the middle

• Playing with the proof (not shown, for good reason) gets you n lg n average-case performance

Pick A Better Pivot

• There are better plans than picking the last element as the pivot

• Simple: take the median value of the first, last and middle elements

• Can move the pivot to the end with a swap

• Way fancier options are available

• Constant factors better: Wikipedia suggests 2-3x faster than Heapsort (next week) or Mergesort in typical practice