Randomised quicksort on a sorted array of eight keys costs 28 comparisons with a fixed pivot, has an expectation of 2369/140 with a random one, and averaged 415/24 over 120 seeds. Those are three different kinds of number and the lesson is that none of them is either of the others. The exact distribution is computed by recursion over subproblem sizes, checked against the closed form, and checked again against running the algorithm on every input order.
Core ideas
The hard idea is that the second number is not an average of runs. The other two are what changes when the input moves and what changes when the seeds move.
Fix the input and the fixed-pivot rule and there is one number: on a sorted array of eight keys, 28 comparisons, and running it again gives 28 again. Fix the input and randomise the pivot and there is no single number — there is a distribution, and on this input it puts weight on every count from 13 to 28. The lab draws it as bars. E[C] = 2369/140 is one summary of that shape, and P(C = 16) = 73/360 is another.
rqsPmf builds the distribution by recursion on subproblem sizes: D(k) = (k − 1) + (1/k)·Σᵢ D(i) ⊛ D(k − 1 − i), with every weight an exact rational. No run is involved and no seed is consulted, so the answer does not move when the seed slider does. It is checked twice — against the closed form 2(n + 1)Hₙ − 4n, which is a different definition, and at small n against running the fixed-pivot algorithm on all n! input orders, which is a different experiment.
Change the array from sorted to alternating high and low and the fixed-pivot count drops from 28 to 16. The exact distribution does not move at all: not the expectation, not the variance, not a single bar. A uniformly random pivot position selects a uniformly random rank whatever order the keys arrived in, so the randomness is the algorithm's and not the data's, and that is the entire content of randomising the pivot.
The material
The count on one input, the expectation over every execution, the mean over the seeds shown — and two checks that the middle one is right.
Quicksort on a block of length L chooses a pivot, partitions the block against it at a cost of L − 1 comparisons, and recurses on the two pieces. The fixed rule always takes the last element of the block. The random rule takes a uniformly random position in the block, independently at every call. The comparison count C is the total over all partitions, and it is the only cost this lesson measures.
On a sorted array the fixed rule pays the worst case. Every pivot is the largest remaining key, so every partition splits a block of length L into one of length L − 1 and one of length 0, and the total is 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28, which is n(n − 1)/2. It is 28 on the reversed array too, for the mirror-image reason. On the alternating array it is 16. One rule, three inputs, three different counts — and every one of them is that rule's cost on that input for ever.
For each n, D(n) is the probability mass function of the comparison count when every pivot is uniformly random. D(0) and D(1) are the point mass at 0. For k ≥ 2, the first partition costs k − 1, and the pivot's rank is uniform on 1..k, leaving blocks of sizes i and k − 1 − i whose costs are independent. So D(k) is k − 1 plus the average over i of the convolution of D(i) and D(k − 1 − i).
That recursion is over sizes rather than over tapes, which is what makes it cheap: the cost of an execution depends only on how the pivots split the blocks, not on which elements they were. At n = 8 it produces sixteen probabilities, one for each attainable count from 13 to 28, and they add to 1 — a check the panel performs and prints rather than assuming.
P(C = 13) = 1/24, P(14) = 13/72, P(15) = 3/20, P(16) = 73/360, P(17) = 29/840, P(18) = 59/420, P(19) = 31/420, P(20) = 5/84, P(21) = 1/36, P(22) = 11/252, P(23) = 17/1260, P(24) = 1/63, P(25) = 2/315, P(26) = 1/210, P(27) = 1/630 and P(28) = 1/315. The most likely count is 16 and the mean is 2369/140 ≈ 16.92, so the two are not the same number; and the shape is not a smooth hump — P(17) is a sixth of P(16) and a quarter of P(18).
That jaggedness is worth a second look, because it is the first thing a reader expecting a bell curve will try to explain away. It is real. A comparison count is a sum over partitions of L − 1, and the attainable sums at small n are constrained by arithmetic rather than by anything smooth: some totals have many ways to arise and some have few. Nothing about the expectation requires the shape around it to be well behaved, which is exactly why the next lesson's bounds are stated for every distribution and not for nice ones.
For n ≥ 1, the expected number of comparisons made by randomised quicksort on n distinct keys is 2(n + 1)Hₙ − 4n, where Hₙ is the n-th harmonic number. It does not depend on the input.
The derivation is Sorting and Selection's, by indicator variables: the i-th and j-th smallest keys are compared exactly when one of them is the first pivot drawn from the stretch of sorted order between them, which has probability 2/(j − i + 1), and linearity adds the indicators up. This course uses it as an oracle rather than re-deriving it. H₈ = 761/280, so the closed form gives 2·9·761/280 − 32 = 2369/140, and the panel prints it beside the recursion's answer with the word agrees or the word DISAGREES.
At n ≤ 7 the lab does something different again: it runs the fixed-pivot algorithm on every one of the n! input orders and tallies what it counted. At n = 5 that is 120 runs, and the resulting distribution agrees with the recursion value by value, with an expectation of 37/5 from both. The agreement is a theorem, not a coincidence: randomising the pivot on a fixed input and fixing the pivot on a uniformly random input are the same experiment.
That pass also checks something no comparison count can. Every one of those 120 runs is required to have returned a sorted array that is a permutation of its input, and the seeded runs are checked the same way. An unsorted array has a comparison count too, and a sorting arm whose only assertion is a count will report a confident number about a broken sort. The panel's last figure reads yes, all 120 for exactly that reason.
Over seeds 1 to 120 on the sorted array the mean comes out 415/24, which is 17.2917, against an expectation of 16.9214: high by 311/840. On the reversed array the same 120 seeds give 1031/60, and on the alternating array 1003/60, which is below the expectation. The exact distribution is identical in all three cases. Three different measured means, one expectation, and the only thing that changed was an input the expectation does not depend on.
The observed range is the other half of the story: 13 to 27 over those 120 seeds on the sorted array, 13 to 26 on the reversed one, 13 to 28 on the alternating one. The support of the true distribution is 13 to 28 in every case. A measured range is a subset of the support and it is a different object from it — the 120 seeds that never produced 28 do not make 28 impossible, and P(C = 28) = 1/315 says how impossible it is not.
C ≤ n(n − 1)/2 on every execution, because each partition compares the pivot with each other element of its block at most once and each pair of elements ends up in the same block for at most one partition. The panel checks that the support of the exact distribution sits inside that bound rather than quoting it. That is the only always claim on this page; the expectation is not one, and neither is the mean.
Interactive
The fixed rule pays n(n − 1)/2 on this input every time; the random rule has an expectation of 2(n + 1)H − 4n and a spread around it
Method
Name the kind of each number before you compare any two of them.
Over one execution on one input, over every execution on one input, or over the seeds on screen. The fixed count is the first, the expectation and the variance are the second, the mean and the observed range are the third. Two numbers of different kinds are never in conflict, however far apart they sit.
Switch between sorted, reversed and alternating. The fixed count moves from 28 to 28 to 16; the whole exact distribution stays put. Anything that moved with the input was a property of the input, and this lab is built so the split is visible in one click.
The measured mean and the measured range move; nothing else does. If a sentence you were about to write changes when the seed slider moves, it was a sentence about 120 runs, and it should say so.
The closed form and the enumeration over every input order are two independent routes to the same number, and the panel prints both with a verdict. An expectation computed one way and checked nowhere is the easiest thing on this course to get confidently wrong.
The array is 1 2 3 4 5 6 7 8, already sorted, and the two rules are run on it. The first column is one execution; the second is all of them; the third is 120 of them.
Seed 2 costs 13 comparisons and seed 1 costs 23, on the same array, with the same algorithm. Neither is the expectation and neither is an error. The distribution puts 1/24 on 13 and 17/1260 on 23, and both events happened in the first two seeds, which is roughly what those probabilities predict.
The gap between 415/24 and 2369/140 is 311/840, about 0.37 comparisons. It is not evidence that the expectation is wrong, and it is not evidence that it is right: with a variance of 8.19 and 120 samples, a gap of that size is ordinary. The next lesson makes that sentence precise without ever taking a square root.
For a faded rehearsal, set the input to alternating and predict all three numbers before the page redraws. The supplied first move is this: the fixed count is a property of the arrangement and will change, and the exact expectation is a property of the algorithm and will not. Say what the measured mean is likely to do — and then say why “likely” is the strongest word available for it.
You should be able to name the three kinds apart, predict which of them a change of input moves and which a change of seed moves, explain why the expectation does not depend on the arrangement, and give at least two independent routes to the same 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.