Quicksort: Pick a Pivot

Lesson 8 of 11 · 7 min · Free, no account needed

What you will learn

Quicksort: pick a pivot, send smaller items left and bigger right, then do the same on each side.
That split is called a partition. After it, the pivot is in its final place.
A pivot near the middle (the median) halves the work: about n log n. A pivot at the edge, like the first card of a sorted row, gives n x n.

Sort your class by height in seconds. Pick one person: shorter go left, taller go right.
Tap anyone to be the pivot.
Be the partition. The pivot is 160 cm.
Drag each person to the smaller or the bigger side.
Now split, then split the splits.
The machine takes each group's first card as its pivot. Step through the levels.
The row is already sorted, and the pivot is still the first card.
Which picture shows its splits? Tap one, then Check.
With the smallest card as pivot, nothing goes left and everything else goes right, so each level removes just one card. That's n - 1 + n - 2 + ... + 1: n x n territory.
Quicksort.
Quicksort: pick a pivot. Smaller items go left, bigger go right: that's a partition. The pivot is now in its final place.
Then quicksort each side the same way, until every group has one item.
A pivot near the middle halves the groups: about n log n. A pivot at the edge peels off one item at a time: n x n.
Write the partition.
Every card after the pivot goes into smaller or bigger.
Which pivot splits the class evenly?
Slide the pivot through the heights. Check when the split is even.
The median has half the values below it and half above, so it splits the group into two equal halves.
Pivot picker.
Four rows. Tap the pivot that splits each one most evenly. Your partition does the split.
This partition has a bug. Find the card on the wrong side.

Lessons are interactive and need JavaScript. Turn it on to play them.