SKEDSOFT

Design Analysis Of Algorithm

Lower bounds for sorting: In a comparison sort, we use only comparisons between elements to gain order information about an input sequence a1, a2, . . ., an. That is, given two elements ai and aj, we perform one of the tests ai < aj, ai aj, ai = aj, ai aj, or ai > aj to determine their relative order. We may not inspect the values of the elements or gain order information about them in any other way.

In this section, we assume without loss of generality that all of the input elements are distinct. Given this assumption, comparisons of the form ai = aj are useless, so we can assume that no comparisons of this form are made. We also note that the comparisons ai aj, ai aj, ai > aj, and ai < aj are all equivalent in that they yield identical information about the relative order of ai and aj. We therefore assume that all comparisons have the form ai aj.

The decision-tree model: Comparison sorts can be viewed abstractly in terms of decision trees. A decision tree is a full binary tree that represents the comparisons between elements that are performed by a particular sorting algorithm operating on an input of a given size. Control, data movement, and all other aspects of the algorithm are ignored. Figure 8.1 shows the decision tree corresponding to the insertion sort algorithm from Section 2.1 operating on an input sequence of three elements.

Figure 8.1: The decision tree for insertion sort operating on three elements. An internal node annotated by i: j indicates a comparison between ai and aj. A leaf annotated by the permutation π(1), π(2), . . ., π(n) indicates the ordering aπ(1) aπ(2) ··· aπ(n). The shaded path indicates the decisions made when sorting the input sequence a1 = 6, a2 = 8, a3 = 5 the permutation 3, 1, 2 at the leaf indicates that the sorted ordering is a3 = 5 a1 = 6 a2 = 8. There are 3! = 6 possible permutations of the input elements, so the decision tree must have at least 6 leaves.

In a decision tree, each internal node is annotated by i: j for some i and j in the range 1 i, j n, where n is the number of elements in the input sequence. Each leaf is annotated by a permutation π(1), π(2), . . ., π(n). The execution of the sorting algorithm corresponds to tracing a path from the root of the decision tree to a leaf. At each internal node, a comparison ai aj is made. The left subtree then dictates subsequent comparisons for ai aj, and the right subtree dictates subsequent comparisons for ai > aj. When we come to a leaf, the sorting algorithm has established the ordering aπ(1) aπ(2) ··· aπ(n). Because any correct sorting algorithm must be able to produce each permutation of its input, a necessary condition for a comparison sort to be correct is that each of the n! permutations on n elements must appear as one of the leaves of the decision tree, and that each of these leaves must be reachable from the root by a path corresponding to an actual execution of the comparison sort. (We shall refer to such leaves as "reachable.") Thus, we shall consider only decision trees in which each permutation appears as a reachable leaf.

A lower bound for the worst case: The length of the longest path from the root of a decision tree to any of its reachable leaves represents the worst-case number of comparisons that the corresponding sorting algorithm performs. Consequently, the worst-case number of comparisons for a given comparison sort algorithm equals the height of its decision tree. A lower bound on the heights of all decision trees in which each permutation appears as a reachable leaf is therefore a lower bound on the running time of any comparison sort algorithm. The following theorem establishes such a lower bound.

Any comparison sort algorithm requires (n lg n) comparisons in the worst case.

Proof From the preceding discussion, it suffices to determine the height of a decision tree in which each permutation appears as a reachable leaf. Consider a decision tree of height h with l reachable leaves corresponding to a comparison sort on n elements. Because each of the n! permutations of the input appears as some leaf, we have n! l. Since a binary tree of height h has no more than 2h leaves, we have

n! l 2h,

which, by taking logarithms, implies

h

lg(n!)

(since the lg function is monotonically increasing)

 

=

(n lg n)