Comparison Sorting (Sorting)

From Algorithm Wiki
Revision as of 10:17, 15 February 2023 by Admin (talk | contribs) (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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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² )$ $O({1})$ (in-situ) Exact Deterministic
Selection Sort 1962 $O( n² )$ $O({1})$ (in-situ) Exact Deterministic
Merge Sort 1945 $O(n logn)$ $O(n)$ Exact Deterministic
Bubble Sort 1956 $O( n² )$ $O({1})$ (in-situ) Exact Deterministic
Intro Sort 1997 $O(n logn)$ $O(logn)$ Exact Deterministic Time
Heap Sort 1964 $O(n logn)$ $O({1})$ (in-situ) Exact Deterministic Time
Tree sort 1962 $O(n logn)$ $O(n)$ Exact Deterministic Time
Quick Sort 1961 $O( n² )$ $O(logn)$ 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² )$ $O({1})$ (in-situ) Exact Deterministic Time
Shell Sort; (Frank & Lazarus) 1960 $O(n^{1.5})$ $O({1})$ (in-situ) Exact Deterministic Time
Shell Sort; (Pratt) 1971 $O(n log² n)$ $O({1})$ (in-situ) Exact Deterministic Time
Shell Sort; (Sedgewick) 1986 $O(n^{1.{3}3})$ $O({1})$ (in-situ) Exact Deterministic Time
Bitonic Merge Sort Parallel Implementation 1968 $O(log² n)$ $O({1})$? Exact Parallel Time
Thorup's Sorting Algorithm 2002 $O(n loglogn)$ $O(n)$ Exact Deterministic Time
Odd Even Sort Parallel Implementation 1972 $O(n^{2})$ $O({1})$ Exact Parallel Time

Time Complexity graph

Sorting - Comparison Sorting - Time.png

Space Complexity graph

Sorting - Comparison Sorting - Space.png

Pareto Decades graph

Sorting - Comparison Sorting - Pareto Frontier.png