TAOCP 5.3.1 Exercise 27

Section 5.3.1: Minimum-Comparison Sorting

Exercise 27. ▶ [20] Suppose it is known that the configurations $K_1 < K_2 < K_3$, $K_1 < K_3 < K_2$, $K_2 < K_1 < K_3$, $K_2 < K_3 < K_1$, $K_3 < K_1 < K_2$, $K_3 < K_2 < K_1$ occur with respective probabilities .01, .25, .01, .24, .25, .24. Find a comparison tree that sorts these three elements with the smallest average number of comparisons.

Verified: no
Solve time: 4m28s

Solution

We are given the six possible orders of three distinct keys (K_1, K_2, K_3) with their probabilities:

[ \begin{array}{c|c} \text{Order} & \text{Probability} \ \hline K_1 < K_2 < K_3;(123) & 0.01 \ K_1 < K_3 < K_2;(132) & 0.25 \ K_2 < K_1 < K_3;(213) & 0.01 \ K_2 < K_3 < K_1;(231) & 0.24 \ K_3 < K_1 < K_2;(312) & 0.25 \ K_3 < K_2 < K_1;(321) & 0.24 \end{array} ]

A comparison tree is a binary tree where each internal node compares two keys (K_i:K_j); the left branch corresponds to (K_i < K_j) and the right to (K_i > K_j). Each leaf is labeled with one of the six permutations. The average number of comparisons is the sum over leaves of (probability (\times) depth). We want the tree that minimizes this average.

Because the set of permutations consistent with a sequence of comparisons is exactly the set of linear extensions of a partial order, we can compute the minimum expected additional comparisons (f(S)) for any such set (S) by dynamic programming. For (|S|=1), (f(S)=0). For (|S|>1),

[ f(S) = \min_{\text{valid comparison } c} \bigl( P(S) + f(S_{\text{left}}) + f(S_{\text{right}}) \bigr), ]

where (P(S)) is the total probability of (S), and the comparison (c) must split (S) into two nonempty subsets. The overall minimum average is (f(\text{all})).

We evaluate all three possible first comparisons.

First comparison (K_1:K_2)

• (K_1<K_2): (S_L = {123, 132, 312},; P=0.51).
  Optimal continuation: compare (K_1:K_3) → (f(S_L)=0.77).
• (K_1>K_2): (S_R = {213, 231, 321},; P=0.49).
  Optimal continuation: compare (K_2:K_3) → (f(S_R)=0.74).

Total: (1 + 0.77 + 0.74 = 2.51).

First comparison (K_1:K_3)

• (K_1<K_3): (S_L = {123, 132, 213},; P=0.27).
  Optimal continuation: compare (K_2:K_3) → (f(S_L)=0.29).
• (K_1>K_3): (S_R = {231, 312, 321},; P=0.73).
  Optimal continuation: compare (K_1:K_2) → (f(S_R)=1.21).

Total: (1 + 0.29 + 1.21 = 2.50).

First comparison (K_2:K_3)

• (K_2<K_3): (S_L = {123, 213, 231},; P=0.26).
  Optimal continuation: compare (K_1:K_3) → (f(S_L)=0.28).
• (K_2>K_3): (S_R = {132, 312, 321},; P=0.74).
  Optimal continuation: compare (K_1:K_3) → (f(S_R)=1.23).

Total: (1 + 0.28 + 1.23 = 2.51).

The minimum average is (2.50), achieved by first comparing (K_1:K_3). The optimal tree is:

1. Compare (K_1 : K_3).
   • If (K_1 < K_3):
     Compare (K_2 : K_3).
     • If (K_2 < K_3):
       Compare (K_1 : K_2).
       • (K_1 < K_2) → order (1;2;3).
       • (K_1 > K_2) → order (2;1;3).
     • If (K_2 > K_3): order (1;3;2).
   • If (K_1 > K_3):
     Compare (K_1 : K_2).
     • If (K_1 < K_2): order (3;1;2).
     • If (K_1 > K_2):
       Compare (K_2 : K_3).
       • (K_2 < K_3) → order (2;3;1).
       • (K_2 > K_3) → order (3;2;1).

The depths and contributions are:

[ \begin{array}{c|c|c} \text{Permutation} & \text{Probability} & \text{Depth} \ \hline 123 & 0.01 & 3 \ 132 & 0.25 & 2 \ 213 & 0.01 & 3 \ 231 & 0.24 & 3 \ 312 & 0.25 & 2 \ 321 & 0.24 & 3 \end{array} \quad\Longrightarrow\quad \text{Average} = 0.01\cdot3 + 0.25\cdot2 + 0.01\cdot3 + 0.24\cdot3 + 0.25\cdot2 + 0.24\cdot3 = 2.50. ]

No other comparison tree yields a smaller average, because the dynamic programming examined every valid first comparison and, for each resulting subset, every valid subsequent comparison, guaranteeing global optimality.

\boxed{2.50}
\boxed{\text{Tree as described above}}

This completes the proof. ∎