TAOCP 5.3.1 Exercise 6

Let keys lie in the ordered set $\{1,2,\dots,m\}$, with $m$ fixed, and let $S_m(n)$ be the worst–case number of comparisons needed by an optimal comparison tree that produces a stable sorted order of...

taocpmathematicsalgorithmsvolume-3

Section 5.3.1: Minimum-Comparison Sorting

Exercise 6. [**] [HM27] When sorting $n$ elements as in exercise 5, and knowing that all keys are members of the set ${1, 2, \dots, m}$, let $S_m(n)$ be the minimum number of comparisons needed in the worst case. [Thus by exercise 6, $S_m(n) = S(n)$.] Prove that, for fixed $m$,

$$S_m(n) \sim n \log_2 m + O(1) \quad \text{as } n \to \infty.$$

12. [M25] (W. G. Bouricius, circa 1954.) Suppose that equal keys may occur, but we merely want to sort the elements ${K_1, K_2, \ldots, K_n}$ so that a permutation $a_1 a_2 \ldots a_n$ is determined with $K_{a_1} < K_{a_2} < \cdots < K_{a_n}$; we do not need to know whether or not equality occurs between $K_{a_i}$ and $K_{a_{i+1}}$.

Let us say that a comparison tree sorts a sequence of keys strongly if it will sort the sequence in the stated sense no matter which branch is taken below the nodes $i:j$ for which $K_i = K_j$. (The tree is binary, not ternary.)

a) Prove that a comparison tree with no redundant comparisons sorts every sequence of keys strongly if and only if it sorts every sequence of distinct keys.

b) Prove that a comparison tree sorts every sequence of keys strongly if and only if it sorts every sequence of zeros and ones strongly.

  1. [M28] Prove (17).
  2. [M24] Find a closed form for the sum (19).
  3. [M21] Determine the asymptotic behavior of $B(n)$ and $F'(n)$ up to $O(\log n)$. [Hint: Show that in both cases the coefficient of $n$ involves the function shown in Fig. 37.]
  4. [HM26] (F. Hwang and S. Lin.) Prove that $F(n) > \lfloor \lg n! \rfloor$ for $n > 22$.
  5. [M20] Prove (29).
  6. [20] If the procedure whose first steps are shown in Fig. 36 had produced the linear graph with efficiency $12!/2^{27}$, would this have proved that $S(12) = 29$?
  7. [40] Experiment with the following heuristic rule for deciding which pair of elements to compare next while designing a comparison tree: At each stage of sorting ${K_1, \ldots, K_n}$, let $u_i$ be the number of keys known to be $< K_i$ as a result of the comparisons made so far, and let $v_i$ be the number of keys known to be $> K_i$, for $1 \le i \le n$. Renumber the keys in terms of increasing $u_i/v_i$, so that $u_1/v_1 < u_2/v_2 < \cdots < u_n/v_n$. Now compare $K_i : K_{i+1}$ for some $i$ that minimizes $|u_i u_{i+1} - v_i v_{i+1}|$. (Although this method is based on far less information than a full comparison matrix as in (24), it appears to give optimum results in many cases.)

20. [M26] Prove that an extended binary tree has minimum external path length if and only if there is a number $l$ such that all external nodes appear on levels $l$ and $l+1$ (or perhaps all on a single level $l$).

  1. [M21] The height of an extended binary tree is the maximum level number of its external nodes. If $x$ is an internal node of an extended binary tree, let $t(x)$ be the number of external nodes below $x$, and let $l(x)$ denote the root of $x$'s left subtree. If $x$ is an external node, let $t(x) = 1$. Prove that an extended binary tree has minimum height among all binary trees with the same number of nodes if

$$|t(x) - 2t(l(x))| < 2^{\lfloor \lg t(x) \rfloor} - t(x)$$

for all internal nodes $x$.

  1. [M24] Continuing exercise 21, prove that a binary tree has minimum external path length among all binary trees with the same number of nodes if and only if

$$|t(x) - 2t(l(x))| < 2^{\lfloor \lg t(x) \rfloor} - t(x)$$

and

$$|t(x) - 2t(l(x))| < t(x) - 2^{\lfloor \lg t(x) \rfloor + 1}$$

for all internal nodes $x$. [Thus, for example, if $t(x) = 67$, we must have $t(l(x)) = 32$, 33, 34, or 35. If we merely wanted to minimize the height of the tree we could have $3 < t(l(x)) < 64$, by the preceding exercise.]

Verified: no
Solve time: 5m39s

Let keys lie in the ordered set ${1,2,\dots,m}$, with $m$ fixed, and let $S_m(n)$ be the worst–case number of comparisons needed by an optimal comparison tree that produces a stable sorted order of $n$ items.

We prove

$$ S_m(n)= n\log_2 m + O(1). $$

Lower bound

A comparison tree of height $h$ has at most $2^h$ leaves.

Each input is a sequence

$$ (K_1,\dots,K_n)\in {1,\dots,m}^n, $$

so there are exactly $m^n$ possible inputs.

A correct stable sorting algorithm must distinguish all these inputs at the level of its computation tree, since each input induces a well-defined sequence of comparison outcomes. Hence the tree must have at least $m^n$ leaves, so

$$ 2^{S_m(n)} \ge m^n. $$

Taking logarithms,

$$ S_m(n) \ge n\log_2 m. $$

Upper bound (correct construction)

We construct a comparison strategy using at most $n\log_2 m + O(1)$ comparisons.

The key idea is to dynamically build and maintain the sorted list of distinct key values that have appeared so far, represented by actual elements.

Maintaining representatives

We maintain a list of representatives

$$ r_1 < r_2 < \cdots < r_k, $$

where each $r_i$ is an input element whose key value is the $i$-th smallest among the distinct key values seen so far. Thus $k \le m$.

The invariant is that the keys of the representatives are strictly increasing and represent all distinct values encountered among processed elements.

Inserting a new element

When processing a new element $x$, we determine its position among the representatives by binary search on the ordered sequence $r_1,\dots,r_k$, using comparisons of the form $x : r_i$.

This is valid because comparisons between elements respect the underlying total order on keys, so the representatives induce a correct ordered structure.

The cost of locating the interval is at most $\lceil \log_2 k\rceil \le \lceil \log_2 m\rceil$ comparisons.

There are two cases:

  1. If $x$ has a key equal to one of the existing representatives, it is placed into the corresponding class (no structural change).
  2. If $x$ has a new key value, it becomes a new representative inserted into the ordered list. Insertion costs $O(k)$ comparisons in the worst case, but this happens at most $m-1$ times.

Thus the total cost of all representative insertions is

$$ \sum_{k=1}^{m-1} O(k)=O(m^2)=O(1) \quad (\text{since } m \text{ is fixed}). $$

Hence maintaining the ordered representative structure over all $n$ elements costs

$$ n\log_2 m + O(1). $$

Producing the sorted output

Once each element has been assigned to its key class (via comparison against representatives), stability implies that within each class the original order of indices is preserved automatically.

Thus no additional comparisons are required: output is obtained by concatenating the classes in the order

$$ r_1 < r_2 < \cdots < r_k. $$

Conclusion

We have shown

$$ n\log_2 m \le S_m(n) \le n\log_2 m + O(1), $$

hence, for fixed $m$,

$$ S_m(n) \sim n\log_2 m + O(1)\quad (n\to\infty). $$

∎