Non-Comparison Sorting: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 42: | Line 42: | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:Sorting - Non-Comparison Sorting - Time.png|1000px]] | [[File:Sorting - Non-Comparison Sorting - Time.png|1000px]] | ||
== Space Complexity | == Space Complexity Graph == | ||
[[File:Sorting - Non-Comparison Sorting - Space.png|1000px]] | [[File:Sorting - Non-Comparison Sorting - Space.png|1000px]] | ||
== Pareto | == Pareto Frontier Improvements Graph == | ||
[[File:Sorting - Non-Comparison Sorting - Pareto Frontier.png|1000px]] | [[File:Sorting - Non-Comparison Sorting - Pareto Frontier.png|1000px]] | ||
Revision as of 13:03, 15 February 2023
Description
A sorting algorithm is an algorithm that puts elements of a list in a certain order, not using comparisons between elements (so elements are typically integers or real numbers).
Related Problems
Generalizations: Sorting
Related: Comparison Sorting
Parameters
n: size of list
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| 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 | |
| Naive sorting | 1940 | $O( n² )$ | $O({1})$ (in-situ) | Exact | Deterministic | |
| Flash Sort | 1998 | $O(n^{2})$ | $O(n)$ | Exact | Deterministic | Time |
| 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 |
| Spaghetti Sort Parallel Implementation | 1984 | $O(n)$ | $O({1})$ auxiliary? per processor? | Exact | Parallel | Time |
Time Complexity Graph
Space Complexity Graph
Pareto Frontier Improvements Graph
