# 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

partitionan arraya:

i← 0

j← |a|

p←a[j]

loop

do

i←i+ 1

whilea[i] <p

do

j←j- 1

whilea[j] >p

ifi≥j

returnj

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

^{2})

### 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