click below
click below
Normal Size Small Size show me how
Sorting Algorithms
WCRT, Runspace, Stability
Algorithm | Characteristics |
---|---|
Selection Sort | WCRT: Θ(n2) Runspace: in place Stable: no Generic: Forward iterators Comment: Improves to linear as input approaches sorted |
Insertion Sort | WCRT: Θ(n2) Runspace: in place Stable: yes Generic: Bidirectional |
Heapsort | WCRT: Θ(n log n) Runspace: in place Stable: no Generic: Random Access Comments: Widely spaced Swaps may cause paging |
Quicksort | WCRT: Θ(n2) Runspace: + Θ(n) Stable: no Generic: Smart Bidirectional Comments: AC = Θ(n log n) |
Merge Sort (array) | WCRT: Θ(n log n) Runspace: + Θ(n) Stable: yes Generic: Random Access Comments: Extra space costly in time |
Merge Sort (list) | WCRT: Θ(n log n) Runspace: in place Stable: yes Generic: Member Function Comments: in-place! But Lists are slow. |
Counting Sort | WCRT: Θ(n + k) Runspace: + Θ(k Stable: yes Comment: Function Object argument |
Radix Sort | WCRT: Θ(d(n + k)) Runspace: + Θ(k) Stable: yes |
Bit Sort | WCRT: Θ(nb) Runspace: + Θ(n) Stable: yes Comments: Use Bit function object in counting sort |
Byte Sort | WCRT: Θ(nB) Runspace: + Θ(n) Stable: yes Comments: Use Byte function object in counting sort |