sorting-algorithms.md (1561B)
1 +++ 2 title = "Sorting algorithms" 3 template = "page-math.html" 4 +++ 5 6 # Sorting algorithms 7 8 Specification: 9 10 - input: finite sequence, usually array starting at index 1 11 - output: ordered permutation (ascending) 12 13 Properties: 14 15 - comparison-based: based on comparisons of elements 16 - for these, lowest worst case is Ω(nlogn) 17 - this can be proved using decision trees 18 - can do better using linear algorithms for specific inputs 19 - in-place: use space for input plus a constant amount of extra space 20 - stable: keep order of equal elements (could lead to space issues if it doesn’t happen) 21 - efficient: what’s the best we can do? 22 23 Theta notation & Big O (like ‘classes of functions’) 24 25 - rate of growth of function when input grows to infinity 26 - saying that a function is in a class means that it ‘grows the same way' 27 - first approximation: drop lower-order terms and leading constants 28 - types: 29 - ϴ is asymptotic tight bound (“=“) 30 - O is asymptotic upper bound (“≤”) 31 - Ω is asymptotic lower bound (“≥”) 32 - properties of Big O 33 - $n^a \in O(n^b) \\;\forall 0 < a \leq b$ 34 - $\log_a(n) \in O(n^b)\\;\\;\forall a,b > 0$ 35 - $n^a \in O(b^n)\\;\\;\forall a>0, b>1$ 36 - $\log_an\in O(\log_bn)\\;\\;\forall a,b > 0$ 37 - important summations 38 - $\sum_{i=0}^{n}a^i = \frac{1-a^{n+1}}{1-a}$ 39 - $\sum_{i=1}^{n}i=\frac{n(n+1)}{2}$ 40 41 Algorithms: 42 43 - [Insertion sort](../insertion-sort) 44 - [Merge sort](../merge-sort) 45 - [Heapsort](../heapsort) 46 - [Quicksort](../quicksort) 47 - [Linear-time algorithms](../linear-time-algorithms)