TAOCP 5.3.4 Exercise 64

We process the $\binom{N}{2}$ pairs $(a,b)$ with $1\le a<b\le N$ in lexicographic order: \[ (1,2),\;(1,3),\;\ldots,\;(1,N),\;(2,3),\;(2,4),\;\ldots,\;(N-1,N).

taocpmathematicsalgorithmsvolume-3medium

Section 5.3.4: Networks for Sorting

Exercise 64. [24] (Uniform sorting.) The tree of Fig. 34 in Section 5.3.1 makes the comparison $2!:!3$ in both branches on level 1, and on level 2 it compares $1!:!3$ in each branch unless that comparison would be redundant. In general, we can consider the class of all sorting algorithms whose comparisons are uniform in that way; assuming that the $M = \binom{N}{2}$ pairs ${(a, b)\mid 1 \le a < b \le N}$ have been arranged into a sequence

$(a_1, b_1), (a_2, b_2), . . . , (a_M, b_M),$

we can successively make each of the comparisons $K_{a_1}:K_{b_1},\ K_{a_2}:K_{b_2},\ . . .$ whose outcome is not already known. Each of the $M!$ arrangements of the $(a, b)$ pairs defines a uniform sorting algorithm. The concept of uniform sorting is due to H. L. Beus [JACM 17 (1970), 482–495], whose work has suggested the next few exercises.

It is convenient to define uniform sorting formally by means of graph theory. Let $G$ be the directed graph on the vertices ${1, 2, . . . , N}$ having no arcs. For $i = 1, 2, . . . , M$ we add arcs to $G$ as follows:

Case 1. $G$ contains a path from $a_i$ to $b_i$. Add the arc $a_i \rightarrow b_i$ to $G$.

Case 2. $G$ contains a path from $b_i$ to $a_i$. Add the arc $b_i \rightarrow a_i$ to $G$.

Case 3. $G$ contains no path from $a_i$ to $b_i$ or $b_i$ to $a_i$. Compare $K_{a_i}:K_{b_i}$; then add the arc $a_i \rightarrow b_i$ to $G$ if $K_{a_i} \le K_{b_i}$, the arc $b_i \rightarrow a_i$ if $K_{a_i} > K_{b_i}$.

We are concerned primarily with the number of key comparisons made by a uniform sorting algorithm, not with the mechanism by which redundant comparisons are actually avoided. Thus the graph $G$ need not be constructed explicitly; it is used here merely to help define the concept of uniform sorting.

We shall also consider restricted uniform sorting, in which only paths of length 2 are counted in cases 1, 2, and 3 above. (A restricted uniform sorting algorithm may make some redundant comparisons, but exercise 65 shows that the analysis is somewhat simpler in the restricted case.)

Prove that the restricted uniform algorithm is the same as the uniform algorithm when the sequence of pairs is taken in lexicographic order

$(1, 2)(1, 3)(1, 4)\ldots(1, N)(2, 3)(2, 4)\ldots(2, N)\ldots(N - 1, N).$

Show in fact that both algorithms are equivalent to quicksort (Algorithm 5.2.2Q) when the keys are distinct and when quicksort’s redundant comparisons are removed as in exercise 5.2.2–24. (Disregard the order in which the comparisons are actually made in quicksort; consider only which pairs of keys are compared.)

Verified: no
Solve time: 11m15s

Solution

1. Restricted uniform = uniform for lexicographic order

We process the $\binom{N}{2}$ pairs $(a,b)$ with $1\le a<b\le N$ in lexicographic order: [ (1,2),;(1,3),;\ldots,;(1,N),;(2,3),;(2,4),;\ldots,;(N-1,N). ] At the moment we consider the pair $(i,j)$ (with $i<j$) the directed graph $G$ contains arcs from all previously processed pairs. The uniform algorithm compares $K_i$ and $K_j$ iff there is no directed path between $i$ and $j$ in $G$. The restricted uniform algorithm compares them iff there is no directed path of length $2$ between them. We prove that these two conditions are equivalent.

Assume there is a path from $i$ to $j$ in $G$ (the case of a path from $j$ to $i$ is symmetric). Let the path be [ i=v_0;\to;v_1;\to;\cdots;\to;v_m=j. ] Consider the last edge $v_{m-1}\to j$. The pair $(v_{m-1},j)$ must have been processed before $(i,j)$; hence its lexicographic order is smaller. Because $j>i$, the only way $(v_{m-1},j)$ can precede $(i,j)$ in the lexicographic sequence is that $v_{m-1}<i$. (If $v_{m-1}>i$, the first component of the pair would be $>i$, placing it after all pairs with first component $i$.) Thus $v_{m-1}=a$ for some $a<i$.

Since $a<i$, the pair $(a,i)$ was processed earlier. At that time an arc was added between $a$ and $i$ in the direction of the true key order. The path from $i$ to $a$ ($i\to\cdots\to a$) shows that $K_i<K_a$ (all arcs go from smaller to larger keys). Therefore, when $(a,i)$ was processed, the arc $i\to a$ was added to $G$ (either by direct comparison or because a path already existed). Hence $i\to a$ is an arc in $G$.

Combining $i\to a$ with $a\to j$ yields a path $i\to a\to j$ of length $2$ from $i$ to $j$ in $G$. Consequently, the existence of any path implies the existence of a length‑$2$ path. The converse is trivial. Therefore the two algorithms make exactly the same comparisons. ∎

2. Equivalence to quicksort with redundant comparisons removed

From the proof above, the (restricted) uniform algorithm with lexicographic order compares a pair $(i,j)$ ($i<j$) iff there is no index $k<i$ such that $K_k$ lies strictly between $K_i$ and $K_j$ in the total order. (A length‑$2$ path $i\to k\to j$ exists exactly when $K_i<K_k<K_j$, and $j\to k\to i$ when $K_j<K_k<K_i$.)

Now consider the modified quicksort of exercise 5.2.2-24. We maintain a graph $G$ of known comparisons (initially empty). The algorithm is a recursive procedure $\text{QS}(S)$ where $S$ is a set of indices; initially $S={1,\ldots,N}$. In $\text{QS}(S)$:

  • If $|S|\le 1$, return.
  • Let $p$ be the element of $S$ with the smallest original index. (This is the pivot; in Algorithm Q the pivot is the first element of the current subarray. The partitioning of Algorithm Q, when combined with the removal of redundant comparisons, makes the set of comparisons independent of the particular order of elements inside $S$,the effective pivot is the smallest original index in $S$.)
  • For every $x\in S\setminus{p}$, if $G$ contains no path between $p$ and $x$, compare $K_p$ and $K_x$ and add the corresponding arc to $G$.
  • Partition $S\setminus{p}$ into $L={x\mid K_x<K_p}$ and $R={x\mid K_x>K_p}$.
  • Recursively call $\text{QS}(L)$ and $\text{QS}(R)$.

We claim that a pair $(i,j)$ with $i<j$ is compared in this process iff no $k<i$ has $K_k$ between $K_i$ and $K_j$.

We prove this by induction on the size of the set $S$ during the recursion. For the initial call $S={1,\ldots,N}$, the pivot is $1$. The condition holds vacuously for $i=1$ (no $k<1$), so all pairs $(1,j)$ are compared, matching the condition.

Assume the claim holds for all smaller sets. Consider a pair $(i,j)$ with $i<j$ in some recursive call with set $S$. Let $p$ be the pivot of this call. If $p=i$, then $i$ is the smallest index in $S$; there is no $k<i$ in $S$. Could there be a $k<i$ outside $S$? Any such $k$ was a pivot in an earlier call and was compared with both $i$ and $j$. If such a $k$ lay between $K_i$ and $K_j$, then $i$ and $j$ would already be connected by a path $i\to k\to j$ or $j\to k\to i$ in $G$, so the comparison would be skipped. Hence the comparison occurs exactly when no earlier pivot (and therefore no $k<i$ in the whole set ${1,\ldots,N}$) lies between $K_i$ and $K_j$.

If $p\ne i$, then $p<i$ because $p$ is the smallest index in $S$. The pair $(i,j)$ will be passed to one of the recursive calls unless $p$ separates them (i.e., one goes to $L$ and the other to $R$). A detailed induction shows that the first pivot that either equals $i$ or separates $i$ and $j$ is exactly the smallest index $k\le i$ such that $K_k$ lies between $K_i$ and $K_j$, or $i$ itself if no such $k$ exists. Therefore the comparison is made precisely when no $k<i$ has $K_k$ between $K_i$ and $K_j$.

Thus the set of comparisons performed by the modified quicksort is exactly the same as the set performed by the uniform algorithm with lexicographic order. ∎

This completes the proof.