EECS 3101 York University Instructor: Andy Mirzaian
LOWER BOUND FOR COMPARISON-BASED SORTING
In this handout we consider the question: How efficiently can we sort? Such questions (deter- mining how to best carry out a task) are among the most difficult and intellectually challenging problems of theoretical computer science. It is generally much more difficult to show that an algorithm is ‘‘best possible’’ for a certain task, than to come up with a ‘‘good’’ algorithm for that task. In the latter case, one need only argue about one algorithm — the one that is supposedly ‘‘good’’; in the former case, one must argue about all possible algorithms — even those which one knows nothing about!
To answer the question ‘‘what’s the best way to do a job’’ we must start by fixing the set of tools that may be used to do the job. For the problem at hand, sorting, we will take pairwise comparisons of keys as the available tools. Of course, this leaves out of consideration Bin sorting (which is not based on key comparisons). But, in a sense, we can justify this on the ground that Bin sorting is not a ‘‘general’’ sorting method: it is applicable only if keys have a particular form. At any rate, it’s important to keep in mind that the result we are about to present only applies to sorting algorithms based on comparisons.
Suppose we want to sort n keys K1 , K2 , … , Kn . Let’s assume that all keys are distinct, so that for any Ki , Kj where i ≠ j , either Ki < Kj or Ki > Kj. The main theoretical device we’ll use to analyze our problem is a decision (or comparison) tree. This is a useful way of represent- ing any comparison-based algorithm that sorts n keys (for any given n). Before introducing the formal definition, let’s develop some intuition about decision trees by studying an example.
Example 1: Below is a decision tree that corresponds to one possible algorithm for sorting 3 keys, K1 , K2 , K3 .
1:2 <>
1:3
>> <
2:3 <>
1:3 <
2:3 <
>
The internal nodes of this tree correspond to comparisons the algorithm makes. The labels in those nodes, specify which keys are to be compared. For example the label “1:2” of the root indicates that K1 is to be compared with K2. Depending on the outcome of the comparison in a node, the left or the right branch out of that node is taken. The label of each leaf is the permuta- tion specifying how to rearrange the keys to get them sorted. For example, consider the node with label “2,3,1”. This means that K2
if K1
if K2
else {K2>K3} sorted order of keys is K3 , K2 , K1
Using the intuition we have gained by studying this example, let us now give the formal
definition of a decision tree.
Definition 1: A decision tree of order n is a binary tree so that
(1) It has n! leaves, each labeled by a different permutation of 1, 2, . . . , n.
(2) Internal nodes are labeled by pairs of indices of the form ‘‘i : j’’, 1 ≤ i ≠ j ≤ n.
(3) In the path from the root to a leaf π(1)π(2)…π(n) (π is a permutation of1,2,…,n) there is either a node ‘‘π (i) : π (i + 1)’’ — in which case the path goes from that node to its left child — or ‘‘π(i +1):π(i)’’ — in which case the path goes from that node to its right child — for each 1 ≤ i < n. (The path may contain other nodes too but must contain at least these.)
The idea is that leaves correspond to the possible outcomes of sorting n distinct keys. Inter-
nal node ‘‘i : j’’ corresponds to the comparison of Ki and K j . If the outcome is Ki < K j then the left subtree of the node ‘‘i: j’’ contains the subsequent comparisons made until the order of the keys is determined. Symmetrically, if the outcome is Ki > K j , the right subtree of ‘‘i : j’’ contains the subsequent comparisons. Part (3) of the definition essentially requires that every relationship determined by the algorithm must have been established by actual comparisons: the algorithm cannot ‘‘guess’’.
Any comparison-based algorithm for sorting n keys corresponds to a decision tree of order n. The execution of the algorithm on input sequence of keys K1, K2,…, Kn follows the path from the root to the leaf labeled by the permutation π such that Kπ(1)
3:1 <>
3:2 <
3:1
>
>
3:2 <
><
21 3
32 1
23 1
It is very important to realize that the node labeled "i: j" in the decision tree specifies the com- parison between keys Ki and K j (as given in the initial array),and not the keys that presently hap- pen to be in the ith and jth positions of the array. Note that the decision tree does not mention swaps of array elements: it simply determines the permutation according to which the elements of the array must be rearranged for the keys to be in sorted order.
A node is called redundant in a decision tree, if the outcome of the comparison it represents can be inferred from previous comparisons in the path from the root to that node. A trivial exam- ple of a redundant node is one with the same label as one of its proper ancestors (this corre- sponds to repeating a comparison already made). A less trivial example is illustrated below
31 2
13 2
i:k
j:k
The ‘‘i : k’’ node is redundant since the outcome of the comparison it represents (Ki vs. Kk ) can be inferred from the fact that Ki