6.1. Sorting Part 1¶
6.1.1. Sorting Part 1¶
6.1.1.1. Sorting¶
- Each record contains a field called the key.
- Linear order: comparison.
- Measures of cost:
- Comparisons
- Swaps
6.1.1.6. Bubble Sort¶
6.1.1.8. Selection Sort¶
6.1.1.10. Summary¶
\[\begin{split}\begin{array}{rccc} &\textbf{Insertion}&\textbf{Bubble}&\textbf{Selection}\\ \textbf{Comparisons:}\\ \textrm{Best Case}&\Theta(n)&\Theta(n^2)&\Theta(n^2)\\ \textrm{Average Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n^2)\\ \textrm{Worst Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n^2)\\ \\ \textbf{Swaps:}\\ \textrm{Best Case}&0&0&\Theta(n)\\ \textrm{Average Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n)\\ \textrm{Worst Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n)\\ \end{array}\end{split}\]
6.1.1.11. Code Tuning¶
- General strategy: Test to avoid work
- Balance test cost, success probability, work saved
- "Optimizations" for quadratic sorts:
- Insertion Sort shift vs swaps: Works
- Selection Sort avoid self-swaps: Does not work
- Bubble Sort avoid/count comparisions: Does not work
