TAOCP 5.3.4 Exercise 36

Consider the input vector \(y = \langle n, n-1, \ldots, 1\rangle\).

taocpmathematicsalgorithmsvolume-3medium

Section 5.3.4: Networks for Sorting

Exercise 36. ▶ [22] The network of Fig. 47 involves only adjacent comparisons $[i:i+1]$; let us call such a network primitive.

a) Prove that a primitive sorting network for $n$ elements must have at least $\binom{n}{2}$ comparators. [Hint: Consider the inversions of a permutation.]

b) (R. W. Floyd, 1964.) Let $\alpha$ be a primitive network for $n$ elements, and let $x$ be a vector such that $(x\alpha)_i > (x\alpha)_j$ for some $i < j$. Prove that $(y\alpha)_i > (y\alpha)_j$, where $y$ is the vector $\langle n, n-1, \ldots, 1\rangle$.

c) As a consequence of (b), a primitive network is a sorting network if and only if it sorts the single vector $\langle n, n-1, \ldots, 1\rangle$.

Verified: no
Solve time: 5m20s

Solution

(a)

Consider the input vector (y = \langle n, n-1, \ldots, 1\rangle). It contains exactly (\binom{n}{2}) inversions.
A primitive network uses only adjacent comparators ([k:k+1]). When such a comparator is applied to a sequence:

  • if the two elements are already in order ((a_k \le a_{k+1})), the sequence is unchanged and the inversion count stays the same;
  • if (a_k > a_{k+1}), the comparator swaps them. This eliminates the inversion ((k,k+1)) and does not change the inversion status of any other pair. (For (i<k) the pairs ((i,k)) and ((i,k+1)) simply exchange their inversion status; for (j>k+1) the pairs ((k,j)) and ((k+1,j)) exchange theirs.) Hence the total number of inversions decreases by exactly (1).

Since the final sorted output has (0) inversions, and each comparator reduces the inversion count by at most (1), at least (\binom{n}{2}) comparators are required. ∎

(b)

We proceed by induction on the number of comparators in the primitive network (\alpha).

Base case: (\alpha) has no comparators. Then ((x\alpha)_i = x_i) and ((y\alpha)_i = y_i). Because (y = \langle n, n-1, \ldots, 1\rangle), we have (y_i = n-i+1 > n-j+1 = y_j) for every (i<j). Thus the implication “((x\alpha)_i > (x\alpha)_j \Rightarrow (y\alpha)_i > (y\alpha)_j)” holds (the consequent is always true).

Inductive step: Assume the statement holds for all primitive networks with fewer comparators than (\alpha). Write (\alpha = \beta) followed by a single adjacent comparator ([k:k+1]). Let
(u = x\beta,; u' = y\beta), and let (v, v') be the results after applying ([k:k+1]) to (u, u') respectively.
We are given (v_i > v_j) for some (i<j) and must prove (v'_i > v'_j).

We distinguish cases according to the positions of (i,j) relative to (k,k+1).

  • Case ({i,j}\cap{k,k+1} = \varnothing).
    (v_i = u_i,; v_j = u_j,; v'_i = u'_i,; v'_j = u'_j).
    From (v_i > v_j) we get (u_i > u_j). By the induction hypothesis (applied to (\beta) and input (x)), (u'_i > u'_j). Hence (v'_i > v'_j).

  • Case (i=k,; j=k+1).
    Then (v_k = \min(u_k,u_{k+1}),; v_{k+1} = \max(u_k,u_{k+1})), so (v_k \le v_{k+1}). This contradicts (v_i > v_j); impossible.

  • Case (i<k,; j=k).
    (v_i = u_i,; v_k = \min(u_k,u_{k+1})).
    (u_i > \min(u_k,u_{k+1})) implies (u_i > u_k) or (u_i > u_{k+1}) (or both). By induction, (u'_i > u'_k) or (u'i > u'{k+1}). Hence (u'_i > \min(u'k,u'{k+1}) = v'_k), i.e. (v'_i > v'_k).

  • Case (i=k,; j>k+1).
    (v_k = \min(u_k,u_{k+1}),; v_j = u_j).
    (\min(u_k,u_{k+1}) > u_j) implies (u_k > u_j) and (u_{k+1} > u_j). By induction, (u'_k > u'j) and (u'{k+1} > u'_j). Thus (\min(u'k,u'{k+1}) > u'_j), i.e. (v'_k > v'_j).

  • Case (i=k+1,; j>k+1).
    (v_{k+1} = \max(u_k,u_{k+1}),; v_j = u_j).
    (\max(u_k,u_{k+1}) > u_j) implies (u_k > u_j) or (u_{k+1} > u_j). By induction, (u'_k > u'j) or (u'{k+1} > u'_j). Hence (\max(u'k,u'{k+1}) > u'j), i.e. (v'{k+1} > v'_j).

  • Case (i<k,; j=k+1).
    (v_i = u_i,; v_{k+1} = \max(u_k,u_{k+1})).
    (u_i > \max(u_k,u_{k+1})) implies (u_i > u_k) and (u_i > u_{k+1}). By induction, (u'_i > u'_k) and (u'i > u'{k+1}). Therefore (u'i > \max(u'k,u'{k+1}) = v'{k+1}), giving (v'i > v'{k+1}).

All possibilities are covered, and in each case we obtain (v'_i > v'_j). This completes the induction. ∎

(c)

If (\alpha) is a sorting network, it sorts every input, so in particular it sorts (y = \langle n, n-1, \ldots, 1\rangle).

Conversely, suppose (\alpha) is a primitive network that sorts (y). Assume, for contradiction, that (\alpha) fails to sort some input (x). Then there exist indices (i<j) with ((x\alpha)_i > (x\alpha)_j). By part (b), this implies ((y\alpha)_i > (y\alpha)_j), contradicting the fact that (\alpha) sorts (y). Hence (\alpha) must sort all inputs, i.e., (\alpha) is a sorting network. ∎