Quick sort — Lomuto - Hoare partition, pivot strategies, expected O(n log n), worst case: Exercises

Level 1 — Recognition

(Can you read a partition and name what it does?)

Problem 1.1 (L1)

State, in one sentence each, the single structural difference between Lomuto and Hoare partition that changes how you write the two recursive calls.

Recall Solution

Lomuto returns the pivot's final resting index q; the pivot is already sorted, so you recurse on quicksort(lo, q-1) and quicksort(q+1, hi) — you exclude q.

Hoare returns a split boundary j; the pivot may sit anywhere, and no element is guaranteed sorted yet, so you recurse on quicksort(lo, j) and quicksort(j+1, hi) — you include j on the left.

The word to hold onto: Lomuto returns a position, Hoare returns a boundary.

Problem 1.2 (L1)

For the pivot p chosen as the last element in Lomuto, what does the pointer i mean at every instant during the scan?

Recall Solution

i is the index of the last element known to be smaller than the pivot — the right edge of the "less-than-pivot zone" A[lo..i]. It starts at lo - 1 (the zone is empty). Every time we find A[j] < p we grow the zone by one (i = i+1) and swap that small value into the zone.

Level 2 — Application

(Can you run the mechanics by hand?)

Problem 2.1 (L2)

Run Lomuto partition on [9, 4, 7, 1, 5] with pivot = last element (5). Give the array after the final swap and the returned index q.

Recall Solution

pivot p = 5, i = -1. Scan j = 0..3.

j	A[j]	< 5?	i	array (zone in [])
start	–	–	-1	[ ] 9 4 7 1 5
0	9	no	-1	[ ] 9 4 7 1 5
1	4	yes	0	[4] 9 7 1 5
2	7	no	0	[4] 9 7 1 5
3	1	yes	1	[4 1] 7 9 5

Final swap: swap A[i+1]=A[2] with A[hi]=A[4] → [4, 1, 5, 9, 7]. Returned index q = i + 1 = 2. The pivot 5 sits at index 2, correctly between the smalls {4,1} and the bigs {9,7}.

Problem 2.2 (L2)

Run Hoare partition on [9, 4, 7, 1, 5] with pivot = first element (9). Give every swap and the returned boundary j.

(Look at the figure below to see the two pointers walking toward each other.)

Figure — Quick sort — Lomuto - Hoare partition, pivot strategies, expected O(n log n), worst case

Recall Solution

pivot p = A[lo] = 9, i = -1, j = 5.

Round 1:

do i++ while A[i] < 9: A[0]=9 is not < 9, so i stops at 0.
do j-- while A[j] > 9: A[4]=5 is not > 9, so j stops at 4.
i=0 < j=4 → swap A[0], A[4] → [5, 4, 7, 1, 9].

Round 2:

do i++: A[1]=4<9, A[2]=7<9, A[3]=1<9, A[4]=9 not <9 → i stops at 4.
do j--: A[3]=1 not >9 → j stops at 3.
i=4 >= j=3 → return j = 3.

Result array [5, 4, 7, 1, 9], boundary j = 3. Check: A[0..3] = {5,4,7,1} are all ≤ 9, A[4] = {9} is the rest. Recursion would be quicksort(0, 3) and quicksort(4, 4).

Level 3 — Analysis

(Can you reason about cost and structure?)

Problem 3.1 (L3)

Using the recurrence for the fully balanced case, confirm via the Master Theorem that quicksort is $Θ (n lo g n)$ . State $a$ , $b$ , $f (n)$ and which case fires.

Recall Solution

Balanced partition splits size $n$ into two halves and does $c n$ comparison work: $T (n) = 2 T (n /2) + c n .$ Match to $T (n) = a T (n / b) + f (n)$ : here $a = 2$ , $b = 2$ , $f (n) = c n$ . Compute the watershed exponent: $n^{l o g_{b} a} = n^{l o g_{2} 2} = n^{1} = n$ . Compare $f (n) = c n$ to $n^{1}$ : they grow at the same rate, so the regular (tie) case of the Master Theorem fires, multiplying by an extra $lo g n$ : $T (n) = Θ (n^{l o g_{b} a} lo g n) = Θ (n lo g n) .$

Problem 3.2 (L3)

Show the worst-case recurrence when every pivot peels off exactly one element, and solve it by unrolling (no Master Theorem).

Recall Solution

If the pivot is the min (or max) each time, one side has size $0$ and the other size $n - 1$ , with $c n$ work to partition: $T (n) = T (n - 1) + c n .$ Unroll: $T (n) = c n + c (n - 1) + c (n - 2) + \dots + c \cdot 1 = c \sum_{k = 1}^{n} k = c \frac{n ( n + 1 )}{2} = Θ (n^{2}) .$ This is exactly what Lomuto + last-element pivot on an already-sorted array produces.

Problem 3.3 (L3)

In the average-case comparison count, two sorted-order elements $z_{i}, z_{j}$ are compared with probability $\frac{2}{j - i + 1}$ . Compute the exact expected number of comparisons for $n = 4$ and give the decimal.

Recall Solution

There are $(2 4) = 6$ pairs. Group by the gap $g = j - i$ :

$g = 1$ : three pairs $(1, 2), (2, 3), (3, 4)$ , each prob $\frac{2}{2} = 1$ → $3 \times 1 = 3$ .
$g = 2$ : two pairs $(1, 3), (2, 4)$ , each prob $\frac{2}{3}$ → $2 \times \frac{2}{3} = \frac{4}{3}$ .
$g = 3$ : one pair $(1, 4)$ , prob $\frac{2}{4} = \frac{1}{2}$ → $\frac{1}{2}$ .

$E = 3 + \frac{4}{3} + \frac{1}{2} = \frac{18 + 8 + 3}{6} = \frac{29}{6} \approx 4.8333.$ So on average quicksort makes about $4.83$ comparisons to sort $4$ distinct elements — sanity check: it's below the $(2 4) = 6$ comparisons a full pairwise scan would do.

Level 4 — Synthesis

(Can you combine ideas and predict behaviour?)

Problem 4.1 (L4)

You must sort an array that is 95% duplicate values. A colleague suggests plain Lomuto. Explain what goes wrong, then state the fix and its new cost on an all-equal array of size $n$ .

Recall Solution

What goes wrong: with heavy duplicates, most elements equal the pivot. Lomuto's strict < sends all-equal elements to the right of the zone, so a partition of an all-equal array puts the pivot at one end and leaves a subarray of size $n - 1$ . That is the peel-off-one pattern → recurrence $T (n) = T (n - 1) + c n = Θ (n^{2})$ .

The fix: 3-way (Dutch National Flag) partitioning splits into < p, = p, > p. The entire equal block is placed in final position and skipped by recursion.

New cost on all-equal input: one partition pass groups everything into the = block; both recursive sides are empty. Total work is one linear scan: $Θ (n)$ .

Problem 4.2 (L4)

Median-of-three picks the median of A[lo], A[mid], A[hi] as pivot. On the sorted array [1,2,3,4,5,6,7], show which element becomes the pivot and why this defeats the sorted-array worst case for this step.

Recall Solution

lo = 0 (value 1), hi = 6 (value 7), mid = (0+6)/2 = 3 (value 4). Median of {1, 4, 7} is 4. So the pivot is 4 — the exact middle value of a sorted array. Partitioning around 4 splits [1,2,3] and [5,6,7]: a perfect balanced split instead of peeling one element. That is why median-of-three "kills" the sorted-array worst case: on sorted input the middle-of-endpoints is always the median, giving balanced partitions. Caveat: it is still $O (n^{2})$ theoretically — a cleverly built ("median-of-three killer") array can defeat it. Only Introsort guarantees $Θ (n lo g n)$ .

Level 5 — Mastery

(Can you design, prove, and connect across the whole map?)

Problem 5.1 (L5)

Quicksort's average comparison count is $\approx 2 n ln n \approx 1.39 n lo g_{2} n$ . Merge Sort does $\approx n lo g_{2} n$ comparisons. Compute the ratio of quicksort's comparisons to merge sort's, and explain in one line why quicksort is still usually faster in wall-clock time despite doing more comparisons.

Recall Solution

Ratio $= \frac{1.39 n lo g _{2} n}{1.0 n lo g _{2} n} = 2 ln 2 \approx 1.386$ . So quicksort does about 39% more comparisons than merge sort on average. Why still faster: quicksort is in-place with sequential, cache-friendly memory access and tiny constant factors, whereas merge sort needs $O (n)$ extra memory and out-of-place data movement. The lower constant per operation more than offsets the 39% extra comparisons in practice.

Problem 5.2 (L5)

Adapt partitioning to build Quickselect (find the $k$ -th smallest element). Give the recurrence for its average time and the one-line reason it is $O (n)$ , not $O (n lo g n)$ .

Recall Solution

Idea: partition once to get pivot index q. If q == k, done. If k < q, recurse only into the left side; if k > q, recurse only into the right side. You never recurse into both halves — that is the whole trick.

Average recurrence: each step throws away a constant fraction and recurses on the rest: $T (n) = T (n /2) + c n .$ Solve: unrolling gives $c n + c \frac{n}{2} + c \frac{n}{4} + \dots = c n \cdot \frac{1}{1 - 1/2} = 2 c n = Θ (n)$ . The geometric series sums to a constant times $n$ — no $lo g n$ factor — because we drop one side entirely instead of recursing on both. (Worst case is still $Θ (n^{2})$ ; randomized pivots make the expectation $O (n)$ .)

Problem 5.3 (L5)

Design the recursion-depth cap for Introsort. If it switches from quicksort to heapsort once recursion depth exceeds $2 lo g_{2} n$ , prove the total time is $Θ (n lo g n)$ .

Recall Solution

The cap: track the current recursion depth d. Before recursing, if d > 2\log_2 n, stop quicksorting this subarray and run Heap Sort on it instead.

Proof of $Θ (n lo g n)$ :

Quicksort work is bounded above by the depth limit. Each level of recursion costs $\leq c n$ across all subarrays (partitions at one depth touch disjoint pieces summing to $\leq n$ ). With at most $2 lo g_{2} n$ levels of quicksort, the quicksort portion costs $\leq c n \cdot 2 lo g_{2} n = Θ (n lo g n)$ .
Whenever we bail to heapsort on a subarray of size $m$ , heapsort is $Θ (m lo g m) = O (m lo g n)$ . The subarrays we bail on at the cap are disjoint and sum to $\leq n$ , so all heapsort work totals $\leq O (n lo g n)$ .
Lower bound: any comparison sort needs $Ω (n lo g n)$ comparisons.

Combining, Introsort is $Θ (n lo g n)$ in the worst case — you keep quicksort's fast average behaviour but the depth cap converts the pathological $O (n^{2})$ tail into a guaranteed $O (n lo g n)$ fallback.

Recall Quick self-check (cloze)

Lomuto returns the pivot's final index; Hoare returns a boundary. ::: Quicksort worst case is ::: $Θ (n^{2})$ Quickselect average time is ::: $Θ (n)$ The average comparison count is $\approx 1.39 n lo g_{2} n$ ; the ratio to merge sort is ::: $2 ln 2 \approx 1.386$