Sorting
By Stefan Xenos
| Formal Definition |
Given a sequence of numbers <x1, x2, ..., xn>, a sorting algorithm must compute a
permutation <x'1, x'2, ..., x'n> such that x'1 ≤ x'2 ≤ ≤ x'n
|
| Intuitive Definition |
A sorting algorithm orders a set of objects from smallest to largest. |
| Lower Bound |
A sorting algorithm based on comparing numbers cannot run any faster than Ω(n log n) in the worst case. Any sorting algorithm that beats this must make use of some other property. |
| Name |
Type |
Runtime |
Memory |
Stable |
Type |
Description |
| Insertion Sort |
wc |
O(n2) |
O(1) |
yes |
cmp |
|
| Selection Sort |
wc |
Θ(n2) |
O(1) |
yes |
cmp |
Efficient for very small data sets |
| Bingo Sort |
wc |
O(n2) |
|
|
cmp |
Optimized for sets containing many duplicate keys |
| Bubble Sort |
wc |
O(n2), Ω(n) |
O(1) |
yes |
cmp |
Approaches O(n) runtime if the list is nearly sorted |
| Cocktail sort |
wc |
O(n2), Ω(n) |
O(1) |
no |
cmp |
AKA bidirectional bubble sort. The O(n) best case is more likely than with bubble-sort. |
| Shell's sort
[She59]
|
wc |
O(n log2 n) |
O(1) |
no |
cmp |
Improved insertion sort that compares elements separated by several positions |
| Quick sort |
wc |
O(n2) |
O(n) |
no |
cmp |
Performance of a given run depend on the input and how pivots are chosen. |
| av |
O(n log n) |
O(log n) |
| Randomized quick sort |
wc |
O(n2) |
O(n) |
no |
cmp |
Performance does not depend on the input |
| av |
O(n log n) |
O(log n) |
| Introsort
[Mus97]
|
wc |
O(n log n) |
O(log n) |
no |
cmp |
Combines the worst-case runtime of heapsort with the expected-case runtime of quicksort |
| Multi-key quick sort |
wc |
O(dn log n + dk) |
|
no |
cmp |
Sorts on each digit, like Radix sort, but uses quicksort rather than bucket sort at each step. Designed for sorting strings. |
| Heap sort |
wc |
O(n log n) |
O(1) |
no |
cmp |
Inserts the elements into a heap structure and extracts them one at a time |
| Adaptive heap sort
[LP93]
|
|
|
|
|
cmp |
Takes advantage of existing order in the input |
| Merge sort |
wc |
Θ(n log n) |
O(n) |
|
cmp |
Repeatedly merges sorted sub-lists until all the elements are in the same sorted list |
| Adaptive bitonic sorting
[BN89]
|
wc |
O((n log n) / p) |
|
|
cmp |
Variation on mergesort for parallel processing (PRAC) architectures |
| Bucket sort |
wc |
O(n log n) |
|
yes |
bin |
Approaches the best case if the numbers are evenly distributed |
| av |
O(n log log n) |
|
| Histogram sort |
wc |
O(n log n) |
|
yes |
bin |
An efficient variation of bucket sort which skips the concatenation phase |
| av |
O(n log log n) |
|
| Radix sort |
wc |
Θ(dn + dk) |
|
yes |
bin |
Restricted to integers in the range 0 to dk-1 or strings of length d |
| Counting sort |
wc |
O(n + k) |
|
yes |
bin |
Restricted to integers in the range 0 to k-1 |
| n =
|
Number of elements being sorted |
| k =
|
Number of buckets |
| d =
|
Maximum number of digits |
| p =
|
Number of parallel processors |
| av |
Expected-case time analysis was used |
| wc |
Worst-case time analysis was used |
Most of the non-stable algorithms can be modified to make them stable without seriously affecting their runtimes. ResourcesDescriptions, pseudocode, and analysis for sorting algorithms can be found at: Sorting and Searching Algorithms Animations of many sorting algorithms can be found
here. Many of the sorting algorithms on this page are discussed by Cormen et al in Introduction to Algorithms. Bibliography
| BN89 |
Gianfranco Bilardi and Alexandru Nicolau
"Adaptive bitonic sorting: an optimal parallel algorithm for shared-memory machines,"
SIAM Journal on computing 18, No. 2, 1989, (216-228).
|
| LP93 |
Christos Levopoulos and Ola Petersson
"Adaptive heapsort,"
Journal of Algorithms 14, No. 3, 1993, (395-413).
|
| Mus97 |
David R. Musser"
"Introspective Sorting and Selection Algorithms,"
Software - Practise and Experience 27, No. 8, 1997, (983-993).
|
| She59 |
D. L. Shell
"A high-speed sorting procedure,"
Communications of the ACM 2, No. 7, 1959, (30-32).
|
[Sorting] [Priority Queues]
Copyright © 2002, 2003, 2007 Stefan Xenos
|