TAOCP 5.3.1 Exercise 9
We consider the problem of sorting \(n\) elements when it is known that each key is either \(0\) or \(1\).
Section 5.3.1: Minimum-Comparison Sorting
Exercise 9. [M20] When sorting $n$ elements as in exercise 7, knowing that all keys are 0 or 1, what is the minimum number of comparisons in the worst case?
Verified: no
Solve time: 27m14s
Solution
We consider the problem of sorting (n) elements when it is known that each key is either (0) or (1). A comparison between two keys has three possible outcomes: (<), (=), or (>). We must determine all equalities among the elements; that is, we must partition the elements into the set of (0)s and the set of (1)s (if both values appear), or conclude that all elements are equal. The actual values (0) and (1) need not be distinguished when all elements are equal - the equality pattern is the same in both cases.
Lower bound. We prove that at least (n-1) comparisons are necessary for (n\ge 2). Initially each element forms its own equivalence class of “possibly equal” elements; there are (n) such classes, and their values ((0) or (1)) are unknown. A comparison between two elements from different classes can have three outcomes:
- (=) - the two classes merge into one unknown class (number of unknown classes decreases by (1));
- (<) - the first class becomes known to be (0), the second known to be (1) (decreases by (2));
- (>) - symmetric (decreases by (2)).
An adversary can always answer “(=)” as long as the two classes are not already forced to be different. Since initially no inequalities are known, the adversary can keep answering “(=)” until all elements have been merged into a single class. Each “(=)” answer reduces the number of unknown classes by exactly (1). To reach a single class from (n) classes requires at least (n-1) such answers. Hence any decision tree must have a path of length at least (n-1); i.e., at least (n-1) comparisons are needed in the worst case. (For (n=1) no comparison is needed.)
Upper bound. The following algorithm uses at most (n-1) comparisons. Compare (K_1:K_2). If the result is (=) then compare (K_2:K_3); continue comparing the next element with the previous one as long as the outcome is “(=)”. If at some step we obtain (<) or (>), we then know one element is (0) and the other is (1). We can then determine the value of every remaining element by comparing it with the known (0) (or the known (1)). In the worst case (all elements equal) the algorithm performs the chain of (n-1) comparisons and then stops, having established that all elements are equal.
Thus the minimum worst-case number of comparisons is (0) for (n=1) and (n-1) for (n\ge 2).
\boxed{\begin{cases} 0 & n=1,\ n-1 & n\ge 2. \end{cases}}
∎