Partition, then look at where the pivot landed: if its rank is the one you wanted you are finished, and otherwise the answer is on one known side and the other side can be discarded entirely. One recursive call instead of two turns n log n into expected linear, because a pivot in the middle half occurs with probability one half and leaves at most three quarters of the range.
Core ideas
The hard idea is that discarding one side changes the recurrence's shape, and that a pivot does not have to be good to be good enough.
Quicksort's recurrence has two recursive terms because both sides still have to be sorted. Quickselect's has one, because the rank you want lies on exactly one side and the other side is thrown away, unexamined. Summing the sizes down a single chain that shrinks by a constant factor gives a geometric series and a linear total, where summing over a branching tree gives n per level and log n levels.
Call a pivot good if its rank lies between n/4 and 3n/4. A uniformly random pivot is good with probability one half, and a good pivot leaves at most 3n/4 elements for the next call. So the expected number of partitions before the range shrinks by a quarter is two, and the sizes fall geometrically. The substitution method sharpens the constant to 4n, which is the reference line the lab prints.
On the lab's 24-key array, seed 5 costs 35 comparisons and seed 1 costs 108, against merge sort's 83 for sorting the whole array. So one draw can lose to sorting, and one draw can exceed 4n = 96. Over 200 seeds the mean is 59.6. The claim is about that mean; a single count is one sample of it, and the lab says so in the sentence under the plot.
The material
The algorithm, the recurrence with one term, the expected-linear argument, and the spread a single run can show.
The k-th order statistic of n values is the k-th smallest of them. The first is the minimum, the n-th is the maximum, and the median is the ⌈n/2⌉-th. Finding one is the selection problem.
Quickselect finds the k-th smallest of a[lo..hi]. Partition the range; let q be the pivot's index and r its rank within the range. If r = k, return the pivot. If k < r, recurse on a[lo..q−1] for the same k; otherwise recurse on a[q+1..hi] for k − r. The other side is never looked at again.
Everything about the partition is unchanged, so a call on a range of m elements still costs m − 1 comparisons. What changed is that only one of the two pieces is visited.
With the pivot of each call drawn uniformly at random from that call's range, the expected number of comparisons quickselect makes on n elements is less than 4n, for every input and every k.
Call a pivot good if its rank within the range lies in the middle half. A uniformly drawn pivot is good with probability at least one half, and a good pivot leaves a range of at most 3n/4 for the next call.
So the expected number of calls spent before the range first drops to 3n/4 or below is at most two, and each of those calls costs less than n. Charging that to a size class, the expected total is at most 2n(1 + 3/4 + 9/16 + …) = 8n, which is already linear.
The constant is loose because a bad pivot still shrinks the range. Solving T(n) ≤ (1/n)Σ T(m) + (n − 1), with the sum over the m from ⌈n/2⌉ to n − 1 that a pivot can leave, by substitution gives T(n) ≤ 4n, and that is the line the lab draws.
□
The array is a seeded shuffle of 1 … 24, and the twelfth smallest is 12. Three partitions find it: the range 1–24 shrinks to 12–24, then to a single element. 35 comparisons, against merge sort's 83 for sorting the array and indexing into it — a baseline counted by an implementation written for another course that has never heard of this one.
Change the seed and the count moves: 108 at seed 1, 57 at seed 2, 86 at seed 3, 35 at seed 5. Over 200 seeds the mean is 59.6 and the extremes are 23 and 118. Two of those draws are above the 4n = 96 reference line, which is allowed: 4n bounds the expectation, not each run. A reader who takes a single count as the bound will see it violated and conclude the wrong thing.
Take the first element as the pivot and ask for the median of an already sorted array of 24: the pivot is the smallest key every time, one element is discarded per call, and the lab measures 210 comparisons against merge sort's 52 on the same array. Selection lost, badly, and for exactly the reason “Quicksort and Its Worst Case” gave. “Median of Medians” removes the randomness instead of relying on it.
One place this matters outside the course: System Design's “Percentiles from a Sample” finds the ⌈qn⌉-th sorted value of a latency sample by sorting the sample and indexing into it. That is Θ(n log n) for a single order statistic, and selection would do it in expected linear time — the same answer, the same rank, one recursive call per level instead of a full sort.
Interactive
One recursive call instead of two, and the range that disappears each time
Method
The procedure is short. The discipline is in what you say about the number it produces.
The rank is the pivot's position within the range, not within the whole array, and getting that wrong is the commonest implementation bug. Compare it with the k you are looking for.
If k is below the rank, everything from the pivot rightwards is gone; otherwise everything leftwards is, and k is reduced by the rank. Write the new k down explicitly. The lab draws the surviving range as a bar so the discarding is visible.
Or until the pivot's rank is k exactly, which can happen at any depth. Count the partitions: three on the worked run, and the lab's calls counter reports them.
Merge sort's total on the same array, counted by running it. 35 against 83 on the worked run. If selection is not beating a full sort, say so: on a deterministic pivot rule and the wrong array it will not, and 210 against 52 is what that looks like.
One seed is one draw. Over 200 of them the count ranges from 23 to 118 with a mean of 59.6, and two of those numbers straddle the 4n reference line. Report the mean as the expectation's neighbour and the single run as a sample.
The array is the lab's seeded shuffle of 1 … 24, the pivot rule is a seeded random element, and the seed is 5. The rank asked for is 12, which on this array is the median, and the value is 12.
The first call discarded eleven elements and the second discarded twelve, and neither discarded side was ever examined again. That is the one recursive term made concrete: 23 + 12 comparisons rather than the 83 a full sort spends, and the saving is not in the partition, which is identical, but in the half of the work that never happens.
Three of those numbers deserve to be kept apart. 35 is a measurement on one array with one seed. 59.6 is a mean over 200 seeds, which is a sample of the expectation. 96 is 4n, a bound on the expectation, and the high draw of 118 is above it, as a single run is entitled to be.
For a faded rehearsal, keep the array and change the rank to 1, the minimum. The supplied first move is a prediction about the shape: the answer is always in the left piece unless the pivot is the minimum itself, so the ranges should shrink from the right. Predict whether selecting the minimum is cheaper than selecting the median, then check it over a few seeds — and say why the expected-linear argument does not care which k was asked for.
You should be able to run quickselect on paper with the ranks and the shifted k written down, state the recurrence with one term, give the good-pivot argument, and distinguish a single measured count from the mean over seeds and from the bound on the expectation.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.