Worst-Case Number of Comparisons in Sorting: A Model of Algorithm A

[This page is auto-generated; please prefer to read the article’s PDF Form.]

[Prev] [Up] [Next]

A Model of Algorithm A

When algorithm A begins, each of the n! permutations can possibly be the sorted permutation. When A makes its 1^st comparison between some elements a_i and a_j, if the order comes out to be a_i < a_j (say), the best it “knows” is that any permutation in which a_i appears after a_j cannot be the sorted one. Thus, after this comparison, A is left with all those permutations in which a_i appears before a_j, and each of these again can possibly be the sorted one. It is only by another comparison between some elements that A would perhaps be further reducing this left-out set of permutations.

Thus, at any point during execution of A, there is a set of permutations each of which can possibly be the sorted permutation, and the sorted permutation must belong to this set. We will call this set the “set of candidate permutations”, and denote it as S. By a sequence of comparisons, A keeps gathering “knowledge” about the elements’ order, which eﬀectively keeps reducing S, until it is left with only 1 permutation in S; this single permutation must be the sorted one.

What we have discussed above is only a model of the algorithm A; it may be called a Model of Candidate Permutations. Many examples of A, like Insertion Sort and Quick Sort, do not actually maintain any set of candidate permutations. The “knowledge” they gather by doing comparisons is recorded by them in the form of their program state, like a sorted subarray or array partitions created based on a pivot. The partial sorted order thus recorded is in fact a representation of the set of candidate permutations.

The above described model of A can be expressed as below. a_i is represented as a_i and a_j as a_j. P is the set of all permutations in S with a_i occurring before a_j, and Q is the set of all the remaining ones (S ∖ P).

S <- (set of all n! permutations)

while(|S| > 1)
{
  if(f(a_i, a_j))
    S <- P
  else
    S <- Q
}

/* Output the single permutation left in S as the sorted one */

Note that after any k number of iterations, each permutation in S is consistent with the output of all k comparisons made so far. For example, if two of these comparisons returned a₂ < a₁ and a₅ < a₂, each permutation in S must have a₅ appearing before a₂, and a₂ appearing before a₁.

Also, since subsets P and Q are simply two partitions of set S, the larger of P and Q must have cardinality at least |S|∕2.

This model of algorithm A extracts from A only its sequence of comparisons and attaches to that sequence a set S of all permutations possible under the comparison responses gathered so far. As long as S contains more than one permutation, A has no way to tell the correct sorted permutation; if it makes any “guess”, that can be wrong. So, A cannot terminate until S has only one permutation left.

[Prev] [Up] [Next]