TAOCP 5.2.2 Exercise 25

We consider Program Q (quicksort) as described in Section 5.

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.2.2: Sorting by Exchanging

Exercise 25. [M20] When the input keys are the numbers $1\ 2\ \ldots\ N$ in order, what are the exact values of the quantities $A$, $B$, $C$, $D$, $E$, and $S$ in the timing of Program Q? (Assume that $N > M$.)

Verified: no
Solve time: 11m16s

Solution

We consider Program Q (quicksort) as described in Section 5.2.2. The six quantities appearing in its timing analysis are:

  • (A) = number of partitioning stages (executions of step Q3),
  • (B) = number of exchanges of two records during partitioning,
  • (C) = number of comparisons between keys during partitioning,
  • (D) = number of times a subfile is pushed onto the stack,
  • (E) = number of times a subfile is popped from the stack,
  • (S) = number of times the straight‑insertion sort (Algorithm 5.2.1S) is invoked.

The input is the already sorted sequence (1,2,\ldots,N) with (N > M). The pivot is always the first element of the current subfile (location (\texttt{INPUT}+L)). Because the keys are in increasing order, the first element is the smallest key in the subfile.

Behavior of one partitioning stage

Let the current subfile have size (n = R-L+1 > M). During partitioning (step Q3):

  • The first inner loop compares (K_I) with the pivot. Since (K_{L+1} > K_L), the test fails immediately → 1 comparison.
  • The second inner loop compares (K_J) with the pivot for (J = R, R-1, \ldots, L). All keys are larger than the pivot until (J = L), where equality holds → (n) comparisons.
  • No exchange of two distinct records ever occurs because the indices never satisfy (I < J) → 0 exchanges.
  • After the loop the pivot is exchanged with (R_J); here (J = L) so this is a self‑exchange and does not count as an exchange of two records.
  • The partition places the pivot at position (L), leaving a left subfile of size (0) and a right subfile of size (n-1). The larger subfile (right) is pushed onto the stack ((D) increases by 1) and the smaller subfile (left, size 0) becomes the new current subfile.

Thus a partitioning stage on a subfile of size (n) contributes [ A \gets A+1,\quad B \gets B,\quad C \gets C+(n+1),\quad D \gets D+1. ]

Overall execution for sorted input

The algorithm starts with the whole file of size (N). Because (N > M), it enters a partitioning stage. The process repeats with the right subfile whose size decreases by 1 each time:

[ N,; N-1,; \ldots,; M+1. ]

There are (N-M) such stages, hence [ A = N-M,\qquad D = N-M. ]

Each of the (N-M) pushed subfiles is later popped exactly once, so [ E = N-M. ]

After the last partition (size (M+1)) we push the subfile of size (M) and process the size‑0 subfile. A subfile of size (0) satisfies (R-L+1 \le M), therefore the insertion sort is called ((S) increases). Then the size‑(M) subfile is popped; it also satisfies the size condition, so insertion sort is called again. No further subfiles remain. Consequently [ S = (N-M) + 1 = N-M+1. ]

Since no exchanges of distinct records ever happen, [ B = 0. ]

The total number of key comparisons is the sum of the comparisons in all partitioning stages: [ C = \sum_{n=M+1}^{N} (n+1) = \sum_{n=M+1}^{N} n ;+; (N-M) = \frac{N(N+1)-M(M+1)}{2} + N-M = \frac{N^2+3N - M^2 - 3M}{2}. ]

Final values

[ \boxed{ \begin{aligned} A &= N-M,\[2pt] B &= 0,\[2pt] C &= \frac{N^2+3N - M^2 - 3M}{2},\[2pt] D &= N-M,\[2pt] E &= N-M,\[2pt] S &= N-M+1. \end{aligned} } ]

This completes the proof. ∎