|
|
|
|
stable sorting algorithm
|
(Definition)
|
|
|
A stable sorting algorithm is any sorting algorithm that preserves the relative ordering of items with equal values. For instance, consider a list of ordered pairs
If a stable sorting algorithm sorts $L$ on the second value in each pair using the $\leq$ relation, then the result is guaranteed to be $\left\{ (C, 2), (A, 3), (E, 4), (B, 5), (D, 5) \right\}$ . However, if an algorithm is not stable, then it is possible that $(D, 5)$ may come before $(B, 5)$ in the sorted output.
Some examples of stable sorting algorithms are bubblesort and mergesort (although the stability of mergesort is dependent upon how it is implemented). Some examples of unstable sorting algorithms are heapsort and quicksort (quicksort could be made stable, but then it wouldn't be quick any more). Stability is a useful property when the total ordering relation is dependent upon initial position. Using a stable sorting algorithm means that sorting by ascending position for equal keys is built-in, and need not be implemented explicitly in the comparison operator.
|
"stable sorting algorithm" is owned by mathcam. [ full author list (3) | owner history (1) ]
|
|
(view preamble | get metadata)
See Also: bubblesort
| Other names: |
stable algorithm |
| Also defines: |
unstable sorting algorithm |
|
|
Cross-references: operator, keys, total ordering, property, quicksort, heapsort, bubblesort, relation, sorts, ordered pairs, ordering, preserves, algorithm
There are 2 references to this entry.
This is version 6 of stable sorting algorithm, born on 2002-03-07, modified 2007-07-10.
Object id is 2756, canonical name is StableSortingAlgorithm.
Accessed 34525 times total.
Classification:
| AMS MSC: | 68P10 (Computer science :: Theory of data :: Searching and sorting) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
