FACTOID # 7: The top five best educated states are all in the Northeast.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Comparison sort

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: In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... In mathematics, a total order, linear order or simple order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ...

1. if ab and ba then a = b (antisymmetry)
2. if ab and bc then ac (transitivity)
3. ab or ba (totalness or trichotomy)

A trichotomy is a splitting into three parts, and, apart from its normal literal meaning, can refer to: trichotomy (mathematics), in the mathematical field of order theory trichotomy (philosophy), for the idea that man has a threefold nature In taxonomy, a trichotomy is speciation of three groups from a common...

Some of the most well-known comparison sorts include:

Some examples of sorts which are not comparison sorts include: Quicksort in action on a list of random numbers. ... A run of the heapsort algorithm sorting an array of randomly permutated values. ... A merge sort algorithm used to sort an array of 7 integer values. ... Introsort or introspective sort is a sorting algorithm designed by David Musser in 1997. ... Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. ... Selection sort is a sorting algorithm, specifically an in-place comparison sort. ... Bubble sort, sometimes shortened to bubblesort, also known as exchange sort, is a simple sorting algorithm. ...

==Performance limits a To meet Wikipedias quality standards, this article may require cleanup. ... Counting sort is a sorting algorithm which (like bucket sort) takes advantage of knowing the range of the numbers in the array to be sorted (array A). ... Bucket sort is a sort algorithm that works by partitioning an array into a finite number of buckets and then sorting each bucket. ...

There are fundamental limits on the performance of comparison sorts. A comparison sort must have a lower bound of Ω(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). The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ... In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor worse than the best possible algorithm. ... The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...

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: In mathematics, a tuple is a finite sequence (also known as an ordered list) of objects, each of a specified type. ... In mathematics, the lexicographical order, or dictionary order, is a natural order structure of the cartesian product of two ordered sets. ...

` function tupleCompare((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) `

Balanced ternary notation allows comparisons to be made in one step, whose result will be one of "less than", "greater than" or "equal to". Balanced ternary is a non-standard positional numeral system, useful for comparison logic. ...

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.

## How many comparisons are needed to sort a list?

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: Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ...

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)geqlog_2(n!)$. The beginning of the sequence of factorials (sequence A000142 in OEIS) In mathematics, the factorial of a number n is the product of all positive integers less than or equal to 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 comparisons in the worst case. The relative difference between (ln x!) and (x ln x - x) approaches zero as x increases. ...

The above argument also provides an absolute, rather than asymptotic, lower bound on the number of comparisons, namely $lceillog_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, $lceillog_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.

## References

Results from FactBites:

 Merge sort - Wikipedia, the free encyclopedia (1255 words) Merge sort's most common implementation does not sort in place, therefore, the memory size of the input must be allocated for the sorted output to be stored in. Merge sort is much more efficient than quicksort if the data to be sorted can only be efficiently accessed sequentially, and is thus popular in languages such as Lisp, where sequentially accessed data structures are very common. Unlike some (inefficient) implementations of quicksort, merge sort is a stable sort as long as the merge operation is implemented properly.
More results at FactBites »

Share your thoughts, questions and commentary here