Sorting - Comparison
Revision as of 11:01, 10 October 2022 by Admin (talk | contribs) (Created page with "== Problem Description== A sorting algorithm is an algorithm that puts elements of a list in a certain order. A Comparison sort compares actual values of the items. The best time complexity that can be reached in comparison based sorting is nlogn. == Bounds Chart == 1050px == Step Chart == 1050px == Improvement Table == {| class="wikitable" style="text-align:center;" width="100%" !width="20%" | Complexity...")
Problem Description
A sorting algorithm is an algorithm that puts elements of a list in a certain order. A Comparison sort compares actual values of the items. The best time complexity that can be reached in comparison based sorting is nlogn.
Bounds Chart
Error creating thumbnail: Unable to save thumbnail to destination
Step Chart
Error creating thumbnail: Unable to save thumbnail to destination
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | ||
| Polynomial > 3 | ||
| Cubic | ||
| Quadratic | Naive sorting (1940) | |
| Selection Sort (1962) | ||
| Bubble Sort (1956) | ||
| Shell Sort; (Shell 1959) (1959) | ||
| Shell Sort; (Frank & Lazarus 1960) (1960) | ||
| Shell Sort; (Pratt 1971) (1971) | ||
| Shell Sort; (Sedgewick; 1986) (1986) | ||
| Odd Even Sort Parallel Implementation (1972) | ||
| nlogn | Merge Sort (1945) | |
| Tree sort (1962) | ||
| Quick Sort (1961) | ||
| Intro Sort (1997) | ||
| Cube Sort Parallel Implementation (1992) | ||
| Heap Sort (1964) | ||
| Linear | Counting Sort (1954) | |
| Tim Sort (2002) | ||
| Flash Sort (1998) | ||
| Bucket Sort (1940) | ||
| Bitonic Merge Sort Parallel Implementation (1968) | ||
| Bead Sort (2002) | ||
| Burst Sort (2004) | ||
| Radix Sort (1940) | ||
| Thorup's Sorting Algorithm (2002) | ||
| Spreadsort (2002) | ||
| Spaghetti Sort Parallel Implementation (1984) | ||
| logn |