Randomised Quicksort and Expected Running Time
Quicksort partitions around a pivot, and its worst case is quadratic. Choosing the pivot at random makes the bad case a matter of luck rather than of input, and the expected running time is n log n whatever the adversary supplies.
What a learner can do afterwards
- Partition an array around a pivot in place and state the invariant of the partition loop
- Construct the input that makes a fixed-pivot quicksort quadratic
- Explain what randomising the pivot changes, and what it does not
1 · Read
Quicksort is divide and conquer in three moves. Partition the array around one pivot so everything smaller sits left and everything bigger sits right, then conquer each side by running the same method on it. Small sides are solved directly, and the sorted pieces join for free since the pivot already sits between them.
Partitioning is one linear scan with two fingers. Finger j walks left to right over each item, while finger q marks the end of the small region. The invariant never breaks: everything left of q is smaller than the pivot. When j finds a small item, it swaps it just past q and both fingers advance; at the end the pivot swaps into place at q.
Fixed pivots have a nightmare: a sorted input where every pick is the smallest or largest remaining item. Then one side takes everything and the other takes nothing, so the problem shrinks by a single item each round and the total work grows like 1 plus 2 plus dot dot dot plus n, which is quadratic. Picking the pivot at random turns this nightmare into mere bad luck: no input can force it anymore, the worst case still exists but grows unlikely, and the expected running time is n log n whatever the adversary supplies.
Keep straight what randomising changes and what it does not. It changes who chooses the bad case: luck, not the input. It does not remove the quadratic worst case, speed up the linear partition scan, or help if the pivot generator itself is rigged.
Partition in one scan, expect luck instead of fearing inputs, and remember the worst case still lurks underneath.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.