Movatterモバイル変換

[0]ホーム

Jump to content

Sorting algorithm

Edit links

From Wikipedia, the free encyclopedia

Algorithm that arranges lists in order

Incomputer science, asorting algorithm is analgorithm that puts elements of alist into anorder. The most frequently used orders arenumerical order andlexicographical order, and either ascending or descending. Efficientsorting is important for optimizing theefficiency of other algorithms (such assearch andmerge algorithms) that require input data to be in sorted lists. Sorting is also often useful forcanonicalizing data and for producing human-readable output.

Formally, the output of any sorting algorithm must satisfy two conditions:

The output is inmonotonic order (each element is no smaller/larger than the previous element, according to the required order).
The output is apermutation (a reordering, yet retaining all of the original elements) of the input.

Although some algorithms are designed forsequential access, the highest-performing algorithms assume data is stored in adata structure which allowsrandom access.

Name	Best	Average	Worst	Memory	Stable	In-place	Method	Other notes
Heapsort	$n\log n$	$n\log n$	$n\log n$	1	No	Yes	Selection	An optimized version of selection sort. Performs selection sort by constructing and maintaining a max heap to find the maximum in $O(\log n)$ time.
Introsort	$n\log n$	$n\log n$	$n\log n$	$\log n$	No	Yes	Partitioning & Selection	Used in severalSTL implementations. Performs a combination of Quicksort, Heapsort, and Insertion sort.
Merge sort	$n\log n$	$n\log n$	$n\log n$	n	Yes	No	Merging	Highly parallelizable (up toO(logn) using the Three Hungarians' Algorithm).^[5]
In-Place Merge Sort	$n\log ^{2}n$	$n\log ^{2}n$	$n\log ^{2}n$	$\log n$	Yes	Yes	Merging	Variation of Mergesort which uses an $O(n\log n)$ in-place stable merge algorithm, such as rotate merge or symmerge.
Tournament sort	$n\log n$	$n\log n$	$n\log n$	n	Yes	No	Selection	An optimization of Selection Sort, which uses a tournament tree to select the min/max.
Tree sort	$n\log n$	$n\log n$	$n\log n$ (balanced)	n	Yes	No	Insertion	When using aself-balancing binary search tree.
Block sort	n	$n\log n$	$n\log n$	1	Yes	Yes	Insertion & Merging	Combine a block-based⁠ $O(n)$ ⁠ in-place merge algorithm^[6] with abottom-up merge sort.
Smoothsort	n	$n\log n$	$n\log n$	1	No	Yes	Selection	Adaptive variant of heapsort based on theLeonardo sequence instead of abinary heap.
Timsort	n	$n\log n$	$n\log n$	n	Yes	No	Insertion & Merging	Makesn-1 comparisons when the data is already sorted or reverse sorted.
Patience sorting	n	$n\log n$	$n\log n$	n	No	No	Insertion & Selection	Finds all thelongest increasing subsequences inO(n logn).
Cubesort	n	$n\log n$	$n\log n$	n	Yes	No	Insertion	Makes $n-1$ comparisons when the data is already sorted or reverse sorted.
Quicksort	$n\log n$	$n\log n$	$n^{2}$	$\log n$	No	Yes	Partitioning	Quicksort can be done in-place withO(logn) stack space.^[7]^[8]
Fluxsort	n	$n\log n$	$n\log n$	n	Yes	No	Partitioning & Merging	An adaptive branchless stable introsort.
Crumsort	n	$n\log n$	$n\log n$	$\log n$	No	Yes	Partitioning & Merging	An in-place, but unstable variant of Fluxsort.
Library sort	$n\log n$	$n\log n$	$n^{2}$	n	No	No	Insertion	Similar to a gapped insertion sort.
Shellsort	$n\log n$ (Ciura)	$n\log n$ (Ciura)	$n^{4/3}$ (Ciura) $n\log ^{2}n$ (Pratt)	1	No	Yes	Insertion	Small code size. Complexity may vary depending on gap sequence. Pratt's sequence has a worst-case of $O(n\log ^{2}n)$ . The (Extended) Ciura sequence averages $O(n\log n)$ empirically.
Comb sort	$n\log n$	$n^{2}$	$n^{2}$	1	No	Yes	Exchanging	Faster than bubble sort on average.
Insertion sort	n	$n^{2}$	$n^{2}$	1	Yes	Yes	Insertion	O(n +d), in the worst case over sequences that havedinversions.
Bubble sort	n	$n^{2}$	$n^{2}$	1	Yes	Yes	Exchanging	Tiny code size.
Cocktail shaker sort	n	$n^{2}$	$n^{2}$	1	Yes	Yes	Exchanging	A bi-directional variant of Bubblesort.
Gnome sort	n	$n^{2}$	$n^{2}$	1	Yes	Yes	Exchanging	Tiny code size.
Odd–even sort	n	$n^{2}$	$n^{2}$	1	Yes	Yes	Exchanging	Can be run on parallel processors easily.
Strand sort	n	$n^{2}$	$n^{2}$	n	Yes	No	Selection
Selection sort	$n^{2}$	$n^{2}$	$n^{2}$	1	No	Yes	Selection	Tiny code size. Noted for its simplicity and small number of element moves. Makes exactly $n {\displaystyle n}$ swaps.
Exchange sort	$n^{2}$	$n^{2}$	$n^{2}$	1	No	Yes	Exchanging	Tiny code size.
Cycle sort	$n^{2}$	$n^{2}$	$n^{2}$	1	No	Yes	Selection	In-place with theoretically optimal number of writes.

Name	Best	Average	Worst	Memory	Stable	n ≪ 2^k	Notes
Pigeonhole sort	—	$n+2^{k}$	$n+2^{k}$	$2^{k}$	Yes	Yes	Cannot sort non-integers.
Bucket sort (uniform keys)	—	$n+k$	$n^{2}\cdot k$	$n\cdot k$	Yes	No	Assumes uniform distribution of elements from the domain in the array.^[11] Also cannot sort non-integers.
Bucket sort (integer keys)	—	$n+r$	$n+r$	$n+r$	Yes	Yes	Ifr is⁠ $O(n)$ ⁠, then average time complexity is⁠ $O(n)$ ⁠.^[12]
Counting sort	—	$n+r$	$n+r$	$n+r$	Yes	Yes	Ifr is⁠ $O(n)$ ⁠, then average time complexity is⁠ $O(n)$ ⁠.^[11]
LSD Radix Sort	$n {\displaystyle n}$	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	Yes	No	${\frac {k}{d}}$ recursion levels, 2^d for count array.^[11]^[12] Unlike most distribution sorts, this can sort non-integers.
MSD Radix Sort	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	Yes	No	Stable version uses an external array of sizen to hold all of the bins. Same as the LSD variant, it can sort non-integers.
MSD Radix Sort (in-place)	—	$n\cdot {\frac {k}{1}}$	$n\cdot {\frac {k}{1}}$	$2^{1}$	No	No	d=1 for in-place, $k/1$ recursion levels, no count array.
Spreadsort	n	$n\cdot {\frac {k}{d}}$	$n\cdot \left({{\frac {k}{s}}+d}\right)$	${\frac {k}{d}}\cdot 2^{d}$	No	No	Asymptotic are based on the assumption thatn ≪ 2^k, but the algorithm does not require this.
Burstsort	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	No	No	Has better constant factor than radix sort for sorting strings. Though relies somewhat on specifics of commonly encountered strings.
Flashsort	n	$n+r$	$n^{2}$	n	No	No	Requires uniform distribution of elements from the domain in the array to run in linear time. If distribution is extremely skewed then it can go quadratic if underlying sort is quadratic (it is usually an insertion sort). In-place version is not stable.
Postman sort	—	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	—	No	A variation of bucket sort, which works very similarly to MSD Radix Sort. Specific to post service needs.
Recombinant sort	$n+r$	$n+r$	$n+r$	$n k {\displaystyle nk}$	No	No	Hashing, Counting, Dynamic Programming, Multidimensional data

Name	Best	Average	Worst	Memory	Stable	Comparison	Other notes
Bead sort	n	S	S	$n^{2}$	—	No	Works only with positive integers. Requires specialized hardware for it to run in guaranteed⁠ $O(n)$ ⁠ time. There is a possibility for software implementation, but running time will be⁠ $O(S)$ ⁠, whereS is the sum of all integers to be sorted; in the case of small integers, it can be considered to be linear.
Merge-insertion sort	$n\log n$ comparisons	$n\log n$ comparisons	$n\log n$ comparisons	Varies	No	Yes	Makes very few comparisons worst case compared to other sorting algorithms. Mostly of theoretical interest due to implementational complexity and suboptimal data moves.
"I Can't Believe It Can Sort"^[13]	$n^{2}$	$n^{2}$	$n^{2}$	1	No	Yes	Notable primarily for appearing to be an erroneous implementation of eitherInsertion Sort orExchange Sort.
Spaghetti (Poll) sort	n	n	n	$n^{2}$	Yes	Polling	This is a linear-time, analog algorithm for sorting a sequence of items, requiringO(n) stack space, and the sort is stable. This requiresn parallel processors. Seespaghetti sort § Analysis.
Sorting network	Varies	Varies	Varies	Varies	Varies (stable sorting networks require more comparisons)	Yes	Order of comparisons are set in advance based on a fixed network size.
Bitonic sorter	$\log ^{2}n$ parallel	$\log ^{2}n$ parallel	$n\log ^{2}n$ non-parallel	1	No	Yes	An effective variation of Sorting networks.^{[disputed –discuss]}
Bogosort	n	$(n\times n!)$	Unbounded	1	No	Yes	Random shuffling. Used for example purposes only, as even the expected best-case runtime is awful.^[14] Worst case is unbounded when using randomization, but a deterministic version guarantees $O(n\times n!)$ worst case.
Stooge sort	$n^{\log 3/\log 1.5}$	$n^{\log 3/\log 1.5}$	$n^{\log 3/\log 1.5}$	n	No	Yes	Slower than most of the sorting algorithms (even naive ones) with a time complexity ofO(n^{log 3 / log 1.5}) =O(n^2.7095...) Can be made stable, and is also asorting network.
Slowsort	$n^{\Omega (\log n)}$	$n^{\Omega (\log n)}$	$n^{\Omega (\log n)}$	n	No	Yes	A multiply and surrender algorithm, antonymous withdivide-and-conquer algorithm.
Franceschini's method^[15]	$-$	$n\log n$	$n\log n$	1	No	Yes	MakesO(n) data moves in the worst case. Possesses ideal comparison sort asymptotic bounds but is only of theoretical interest.

v t e Data structures andalgorithms
Data structures	Array Associative array Binary search tree Fenwick tree Graph Hash table Heap Linked list Queue Segment tree Stack String Tree Trie
Algorithms andalgorithmic paradigms	Backtracking Binary search Breadth-first search Brute-force search Depth-first search Divide and conquer Dynamic programming Graph traversal Fold Greedy Hash function Minimax Online Randomized Recursion Root-finding Sorting Streaming Sweep line String-searching Topological sorting
List of data structures List of algorithms

v t e Sorting algorithms
Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Proportion extend sort Quicksort
Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Kirkpatrick–Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort
Impractical sorts	Stooge sort Slowsort Bogosort

Movatterモバイル変換

History and concepts

Classification

Stability

Comparison of algorithms

Comparison sorts

Non-comparison sorts

Others

Popular sorting algorithms

Simple sorts

Insertion sort

Selection sort

Efficient sorts

Merge sort

Heapsort

Recombinant sort

Quicksort

Shellsort

Bubble sort and variants

Bubble sort

Comb sort

Exchange sort

Distribution sorts

Counting sort

Bucket sort

Radix sort

Memory usage patterns and index sorting

Related algorithms

See also

References

Further reading

External links