6.Sortingยง
- Each record contains a field called the key.
- Linear order: comparison.
- Measures of cost:
- Comparisons
- Swaps
Insertion Sort
Analysis: Worst Case
Analysis: Best Case
Analysis: Average Case
Bubble Sort
Analysis
Selection Sort
Analysis
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}\]
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
Exchange Sorting
- All of the sorts so far rely on exchanges of adjacent records.
- Inversions
- What is the average number of exchanges required?