Comparison sort

From Wikipedia, the free encyclopedia

You have new messages (last change).

A comparison sort is a particular type of sorting algorithm; a number of well-known algorithms are comparison sorts. It is defined as a sorting algorithm which can only read the list elements through a single abstract comparison operation (often a "less than or equal to" operator) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator obey the three defining properties of a total order:

  1. if a ≤ b and b ≤ a then a = b (antisymmetry)
  2. if a ≤ b and b ≤ c then a ≤ c (transitivity)
  3. a ≤ b or b ≤ a (totalness or trichotomy)

Contents

[edit] Examples

Some of the most well-known comparison sorts include:

Some examples of sorts which are not comparison sorts include:

[edit] Performance limits

There are fundamental limits on the performance of comparison sorts. A comparison sort must have an lower bound of at least Ω(n log n) comparison operations in the worst case. This is a consequence of the limited information available through comparisons alone -- or, to put it differently, of the vague algebraic structure of totally ordered sets. In this sense, mergesort, heapsort, and introsort are asymptotically optimal in terms of the number of comparisons they must perform, although this metric neglects other operations. The three non-comparison sorts above achieve O(n) performance by using operations other than comparisons, allowing them to sidestep this lower bound (assuming elements are constant-sized).

Nevertheless, comparison sorts offer the notable advantage that control over the comparison function allows sorting of many different datatypes and fine control over how the list is sorted. For example, reversing the result of the comparison function allows the list to be sorted in reverse, and it's simple to sort a list of tuples in lexicographic order by just creating a comparison function that compares by each part in sequence:

function compare((lefta, leftb, leftc), (righta, rightb, rightc))
    if lefta ≠ righta
        return compare(lefta, righta)
    else if leftb ≠ rightb
        return compare(leftb, rightb)
    else
        return compare(leftc, rightc)

Comparison sorts generally adapt more easily to complex orders such as the order of floating-point numbers. Additionally, once a comparison function is written, any comparison sort can be used without modification; non-comparison sorts typically require specialized versions for each datatype.

This flexibility, together with the efficiency of the above comparison sorting algorithms on modern computers, has led to widespread preference for comparison sorts in most practical work.

[edit] How many comparisons are needed?

The number of comparisons an optimal comparison sort algorithm needs to do increases in proportion to nlog(n), where n is the number of elements to sort. It is easy to prove that this bound is asymptotically tight, as follows:

Imagine we're sorting a list of numbers, all distinct (we can assume this because this is a worst-case analysis). There are n factorial (n!) possible ways to rearrange this list, and each one must be rearranged differently to come up with a sorted list. Thus in order to sort correctly, the sort algorithm must gain enough information from the comparisons to distinguish between the n! different possibilities. As we assume distinct keys, each comparison has only two different possible outcomes, so if the algorithm always completes after at most f(n) steps, it cannot distinguish more than 2f(n) cases. Therefore, for a correct comparison sort it must hold that 2^{f(n)}\geq n!, or equivalently f(n)\geq\log_2(n!).

From Stirling's approximation we know that log2(n!) is asymptotically equal to n \ \log_2 \ n (modulo some terms at most linear in n). This provides the lower-bound part of the claim. An identical upper bound follows from the well-known fact that several of the algorithms mentioned above do perform O(n \ \log \ n) comparisons in the worst case.

The above argument also provides an absolute, rather than asymptotic, lower bound on the number of comparisons, namely \lceil\log_2(n!)\rceil comparisons. This lower bound is fairly good (it can be approached within a linear tolerance by a simple merge sort), but it is known not to be exact. For example, \lceil\log_2(13!)\rceil=33, but the minimal number of comparisons to sort 13 elements has been proved to be 34 (Peczarski 2004).

Determining the exact minimal number of comparisons needed to sort a given number of entries is a computationally hard problem even for relatively small n, and no simple formula for the solution is known. For some of the few concrete values that have been computed, see A036604.

[edit] References

Retrieved from "http://en.wikipedia.org../../../c/o/m/Comparison_sort.html"