Comparison Sorting: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
(Created page with "{{DISPLAYTITLE:Comparison Sorting (Sorting)}} == Description == A sorting algorithm is an algorithm that puts elements of a list in a certain order, using comparisons between elements. == Related Problems == Generalizations: Sorting Related: Non-Comparison Sorting == Parameters == <pre>n: size of list</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approximation...")
 
No edit summary
 
(4 intermediate revisions by the same user not shown)
Line 12: Line 12:
== Parameters ==  
== Parameters ==  


<pre>n: size of list</pre>
$n$: size of list


== Table of Algorithms ==  
== Table of Algorithms ==  
Line 22: Line 22:
|-
|-


| [[Naive sorting (Comparison Sorting Sorting)|Naive sorting]] || 1940 || $O( )$ || $O({1})$ (in-situ) || Exact || Deterministic ||   
| [[Naive sorting (Comparison Sorting Sorting)|Naive sorting]] || 1940 || $O(n^{2})$ || $O({1})$ (in-situ) || Exact || Deterministic ||   
|-
|-
| [[Selection Sort (Comparison Sorting Sorting)|Selection Sort]] || 1962 || $O( )$ || $O({1})$ (in-situ) || Exact || Deterministic ||   
| [[Selection Sort (Comparison Sorting Sorting)|Selection Sort]] || 1962 || $O(n^{2})$ || $O({1})$ (in-situ) || Exact || Deterministic ||   
|-
|-
| [[Merge Sort (Comparison Sorting Sorting)|Merge Sort]] || 1945 || $O(n logn)$ || $O(n)$ || Exact || Deterministic ||   
| [[Merge Sort (Comparison Sorting Sorting)|Merge Sort]] || 1945 || $O(n \log n)$ || $O(n)$ || Exact || Deterministic ||   
|-
|-
| [[Bubble Sort (Comparison Sorting Sorting)|Bubble Sort]] || 1956 || $O( )$ || $O({1})$ (in-situ) || Exact || Deterministic ||   
| [[Bubble Sort (Comparison Sorting Sorting)|Bubble Sort]] || 1956 || $O(n^{2})$ || $O({1})$ (in-situ) || Exact || Deterministic ||   
|-
|-
| [[Intro Sort (Comparison Sorting Sorting)|Intro Sort]] || 1997 || $O(n logn)$ || $O(logn)$ || Exact || Deterministic || [https://onlinelibrary.wiley.com/doi/abs/10.1002/%28SICI%291097-024X%28199708%2927%3A8%3C983%3A%3AAID-SPE117%3E3.0.CO%3B2-%23 Time]
| [[Intro Sort (Comparison Sorting Sorting)|Intro Sort]] || 1997 || $O(n \log n)$ || $O(logn)$ || Exact || Deterministic || [https://onlinelibrary.wiley.com/doi/abs/10.1002/%28SICI%291097-024X%28199708%2927%3A8%3C983%3A%3AAID-SPE117%3E3.0.CO%3B2-%23 Time]
|-
|-
| [[Heap Sort (Comparison Sorting Sorting)|Heap Sort]] || 1964 || $O(n logn)$ || $O({1})$ (in-situ) || Exact || Deterministic || [https://www.bibsonomy.org/bibtex/2f485e4ea9a877871b59ab503151a7f10/bjoern Time]
| [[Heap Sort (Comparison Sorting Sorting)|Heap Sort]] || 1964 || $O(n \log n)$ || $O({1})$ (in-situ) || Exact || Deterministic || [https://www.bibsonomy.org/bibtex/2f485e4ea9a877871b59ab503151a7f10/bjoern Time]
|-
|-
| [[Tree sort (Comparison Sorting Sorting)|Tree sort]] || 1962 || $O(n logn)$ || $O(n)$ || Exact || Deterministic || [http://www.neubert.net/FSOIntro.html Time]
| [[Counting Sort (Non-Comparison Sorting Sorting)|Counting Sort]] || 1954 || $O(n+k)$ || $O(n+k)$ || Exact || Deterministic || [http://bitsavers.org/pdf/mit/whirlwind/R-series/R-232_Information_Sorting_in_the_Application_of_Electronic_Digital_Computers_to_Business_Operations_May54.pdf Time]
|-
|-
| [[Quick Sort (Comparison Sorting Sorting)|Quick Sort]] || 1961 || $O( )$ || $O(logn)$ || Exact || Deterministic || [https://apps.dtic.mil/dtic/tr/fulltext/u2/740110.pdf Time] & [https://academic.oup.com/comjnl/article/5/1/10/395338?login=true Space]
| [[Bucket Sort (Non-Comparison Sorting Sorting)|Bucket Sort]] || 1940 || $O( n² )$ || $O(n)$ || Exact || Deterministic || 
|-
| [[Radix Sort (Non-Comparison Sorting Sorting)|Radix Sort]] || 1940 || $O(wn)$ || $O(w+n)$ || Exact || Deterministic || 
|-
| [[Tree sort (Comparison Sorting Sorting)|Tree sort]] || 1986 || $O(n \log n)$ || $O(n)$ || Exact || Deterministic || [https://link.springer.com/chapter/10.1007/978-1-349-08147-9_4 Time]
|-
| [[Quick Sort (Comparison Sorting Sorting)|Quick Sort]] || 1961 || $O(n^{2})$ || $O(\log n)$ || Exact || Deterministic || [https://apps.dtic.mil/dtic/tr/fulltext/u2/740110.pdf Time] & [https://academic.oup.com/comjnl/article/5/1/10/395338?login=true Space]
|-
|-
| [[Tim Sort (Comparison Sorting Sorting)|Tim Sort]] || 2002 || $O(n logn)$ || $O(n)$ || Exact || Deterministic ||   
| [[Tim Sort (Comparison Sorting Sorting)|Tim Sort]] || 2002 || $O(n logn)$ || $O(n)$ || Exact || Deterministic ||   
Line 42: Line 48:
| [[Cube Sort Parallel Implementation (Comparison Sorting Sorting)|Cube Sort Parallel Implementation]] || 1992 || $O(n logn)$ || $O(n)$ || Exact || Parallel || [https://www.sciencedirect.com/science/article/pii/0196677492900166?via%3Dihub Time]
| [[Cube Sort Parallel Implementation (Comparison Sorting Sorting)|Cube Sort Parallel Implementation]] || 1992 || $O(n logn)$ || $O(n)$ || Exact || Parallel || [https://www.sciencedirect.com/science/article/pii/0196677492900166?via%3Dihub Time]
|-
|-
| [[Shell Sort; (Shell) (Comparison Sorting Sorting)|Shell Sort; (Shell)]] || 1959 || $O( )$ || $O({1})$ (in-situ) || Exact || Deterministic || [https://dl.acm.org/citation.cfm?doid=368370.368387 Time]
| [[Shell Sort (Shell) (Comparison Sorting Sorting)|Shell Sort (Shell)]] || 1959 || $O(n^{2})$ || $O({1})$ || Exact || Deterministic || [https://dl.acm.org/citation.cfm?doid=368370.368387 Time]
|-
|-
| [[Shell Sort; (Frank & Lazarus) (Comparison Sorting Sorting)|Shell Sort; (Frank & Lazarus)]] || 1960 || $O(n^{1.5})$ || $O({1})$ (in-situ) || Exact || Deterministic || [https://dl.acm.org/citation.cfm?doid=366947.366957 Time]
| [[Shell Sort (Frank & Lazarus) (Comparison Sorting Sorting)|Shell Sort (Frank & Lazarus)]] || 1960 || $O(n^{1.5})$ || $O({1})$ || Exact || Deterministic || [https://dl.acm.org/citation.cfm?doid=366947.366957 Time]
|-
|-
| [[Shell Sort; (Pratt) (Comparison Sorting Sorting)|Shell Sort; (Pratt)]] || 1971 || $O(n log² n)$ || $O({1})$ (in-situ) || Exact || Deterministic || [https://apps.dtic.mil/sti/pdfs/AD0740110.pdf Time]
| [[Shell Sort (Pratt) (Comparison Sorting Sorting)|Shell Sort (Pratt)]] || 1971 || $O(n \log^{2} n)$ || $O({1})$ || Exact || Deterministic || [https://apps.dtic.mil/sti/pdfs/AD0740110.pdf Time]
|-
|-
| [[Shell Sort; (Sedgewick) (Comparison Sorting Sorting)|Shell Sort; (Sedgewick)]] || 1986 || $O(n^{1.{3}3})$ || $O({1})$ (in-situ) || Exact || Deterministic || [https://www.sciencedirect.com/science/article/pii/0196677486900015?via%3Dihub Time]
| [[Shell Sort (Sedgewick) (Comparison Sorting Sorting)|Shell Sort (Sedgewick)]] || 1986 || $O(n^{1.{3}3})$ || $O({1})$ || Exact || Deterministic || [https://www.sciencedirect.com/science/article/pii/0196677486900015?via%3Dihub Time]
|-
|-
| [[Bitonic Merge Sort Parallel Implementation (Comparison Sorting Sorting)|Bitonic Merge Sort Parallel Implementation]] || 1968 || $O(log² n)$ || $O({1})$? || Exact || Parallel || [https://epubs.siam.org/doi/abs/10.1137/0218014 Time]
| [[Bitonic Merge Sort Parallel Implementation (Comparison Sorting Sorting)|Bitonic Merge Sort Parallel Implementation]] || 1968 || $O(\log^{2} n)$ || $O({1})$ || Exact || Parallel || [https://epubs.siam.org/doi/abs/10.1137/0218014 Time]
|-
|-
| [[Thorup's Sorting Algorithm (Comparison Sorting Sorting)|Thorup's Sorting Algorithm]] || 2002 || $O(n loglogn)$ || $O(n)$ || Exact || Deterministic || [https://www.sciencedirect.com/science/article/pii/S0196677402912113?via%3Dihub Time]
| [[Thorup's Sorting Algorithm (Comparison Sorting Sorting)|Thorup's Sorting Algorithm]] || 2002 || $O(n \log \log n)$ || $O(n)$ || Exact || Deterministic || [https://www.sciencedirect.com/science/article/pii/S0196677402912113 Time & Space]
|-
| [[Naive sorting (Non-Comparison Sorting Sorting)|Naive sorting]] || 1940 || $O(n^{2})$ || $O({1})$ || Exact || Deterministic || 
|-
| [[Flash Sort (Non-Comparison Sorting Sorting)|Flash Sort]] || 1998 || $O(n^{2})$ || $O(n)$ || Exact || Deterministic || [http://www.neubert.net/FSOIntro.html Time] & [http://www.neubert.net/FSOIntro.html, Space]
|-
| [[Bead Sort (Non-Comparison Sorting Sorting)|Bead Sort]] || 2002 || $O(n)$ || $O(n^{2})$ || Exact || Deterministic || [https://web.archive.org/web/20170809110409/https://www.cs.auckland.ac.nz/~jaru003/research/publications/journals/beadsort.pdf Time]
|-
| [[Burst Sort (Non-Comparison Sorting Sorting)|Burst Sort]] || 2004 || $O(wn)$ || $O(wn)$ || Exact || Deterministic || [https://dl.acm.org/citation.cfm?doid=1005813.1041517 Time]
|-
| [[Spreadsort (Non-Comparison Sorting Sorting)|Spreadsort]] || 2002 || $O(n \log n)$ || $O(n)$? || Exact || Deterministic || [https://www.semanticscholar.org/paper/The-Spreadsort-High-performance-General-case-Ross/41f5b49e9843b2d98b6b22a84924dae5761e6e52 Time]
|-
|-
| [[Odd Even Sort Parallel  Implementation (Comparison Sorting Sorting)|Odd Even Sort Parallel  Implementation]] || 1972 || $O(n^{2})$ || $O({1})$ || Exact || Parallel || [https://www.semanticscholar.org/paper/Parallel-Neighbor-Sort-(or-the-Glory-of-the-Habermann/bc7b6efb99aae6225239425747fd0169a51f30ce Time]
| [[Odd Even Sort Parallel  Implementation (Comparison Sorting Sorting)|Odd Even Sort Parallel  Implementation]] || 1972 || $O(n^{2})$ || $O({1})$ || Exact || Parallel || [https://www.semanticscholar.org/paper/Parallel-Neighbor-Sort-(or-the-Glory-of-the-Habermann/bc7b6efb99aae6225239425747fd0169a51f30ce Time]
|-
| [[Spaghetti Sort Parallel Implementation (Non-Comparison Sorting Sorting)|Spaghetti Sort Parallel Implementation]] || 1984 || $O(n)$ || $O({1})$ auxiliary? per processor? || Exact || Parallel || [https://link.springer.com/chapter/10.1007/978-94-009-2794-0_11 Time]
|-
|-
|}
|}


== Time Complexity graph ==  
== Time Complexity Graph ==  


[[File:Sorting - Comparison Sorting - Time.png|1000px]]
[[File:Sorting - Comparison Sorting - Time.png|1000px]]
== Space Complexity graph ==
[[File:Sorting - Comparison Sorting - Space.png|1000px]]
== Pareto Decades graph ==
[[File:Sorting - Comparison Sorting - Pareto Frontier.png|1000px]]

Latest revision as of 10:04, 28 April 2023

Description

A sorting algorithm is an algorithm that puts elements of a list in a certain order, using comparisons between elements.

Related Problems

Generalizations: Sorting

Related: Non-Comparison Sorting

Parameters

$n$: size of list

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Naive sorting 1940 $O(n^{2})$ $O({1})$ (in-situ) Exact Deterministic
Selection Sort 1962 $O(n^{2})$ $O({1})$ (in-situ) Exact Deterministic
Merge Sort 1945 $O(n \log n)$ $O(n)$ Exact Deterministic
Bubble Sort 1956 $O(n^{2})$ $O({1})$ (in-situ) Exact Deterministic
Intro Sort 1997 $O(n \log n)$ $O(logn)$ Exact Deterministic Time
Heap Sort 1964 $O(n \log n)$ $O({1})$ (in-situ) Exact Deterministic Time
Counting Sort 1954 $O(n+k)$ $O(n+k)$ Exact Deterministic Time
Bucket Sort 1940 $O( n² )$ $O(n)$ Exact Deterministic
Radix Sort 1940 $O(wn)$ $O(w+n)$ Exact Deterministic
Tree sort 1986 $O(n \log n)$ $O(n)$ Exact Deterministic Time
Quick Sort 1961 $O(n^{2})$ $O(\log n)$ Exact Deterministic Time & Space
Tim Sort 2002 $O(n logn)$ $O(n)$ Exact Deterministic
Cube Sort Parallel Implementation 1992 $O(n logn)$ $O(n)$ Exact Parallel Time
Shell Sort (Shell) 1959 $O(n^{2})$ $O({1})$ Exact Deterministic Time
Shell Sort (Frank & Lazarus) 1960 $O(n^{1.5})$ $O({1})$ Exact Deterministic Time
Shell Sort (Pratt) 1971 $O(n \log^{2} n)$ $O({1})$ Exact Deterministic Time
Shell Sort (Sedgewick) 1986 $O(n^{1.{3}3})$ $O({1})$ Exact Deterministic Time
Bitonic Merge Sort Parallel Implementation 1968 $O(\log^{2} n)$ $O({1})$ Exact Parallel Time
Thorup's Sorting Algorithm 2002 $O(n \log \log n)$ $O(n)$ Exact Deterministic Time & Space
Naive sorting 1940 $O(n^{2})$ $O({1})$ Exact Deterministic
Flash Sort 1998 $O(n^{2})$ $O(n)$ Exact Deterministic Time & Space
Bead Sort 2002 $O(n)$ $O(n^{2})$ Exact Deterministic Time
Burst Sort 2004 $O(wn)$ $O(wn)$ Exact Deterministic Time
Spreadsort 2002 $O(n \log n)$ $O(n)$? Exact Deterministic Time
Odd Even Sort Parallel Implementation 1972 $O(n^{2})$ $O({1})$ Exact Parallel Time
Spaghetti Sort Parallel Implementation 1984 $O(n)$ $O({1})$ auxiliary? per processor? Exact Parallel Time

Time Complexity Graph

Sorting - Comparison Sorting - Time.png