Register

# 17.21. Sorting Part 1¶

## 17.21.1. Sorting Part 1¶

### 17.21.1.1. Sorting¶

• Each record contains a field called the key.
• Linear order: comparison.

• Measures of cost:
• Comparisons

• Swaps

### 17.21.1.2. Insertion Sort¶

What would you do if you have a stack of phone bills from the past two years and you want to order by date? A fairly natural way to handle this is to look at the first two bills and put them in order. Then take the third bill and put it into the right position with respect to the first two, and so on.

### 17.21.1.3. Initial Step¶

Consider this start to the process.

Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit

Settings

Saving...
Server Error
Resubmit

### 17.21.1.11. 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}$

### 17.21.1.12. Code Tuning (1)¶

• General strategy: Test to avoid work
• Balance test cost, success probability, work saved

• Insertion Sort shift vs swaps: Works

• Selection Sort viewed as an optimization of Bubble Sort: Works

• Selection Sort avoid self-swaps: Does not work

• Bubble Sort “i” vs “1”: Works

• Bubble Sort count comparisons/avoid unnecessary iterations: Does not work

• Bubble Sort O(n) best case claim (Wikipedia): Bogus

### 17.21.1.13. Exchange Sorting¶

• All of the sorts so far rely on exchanges of adjacent records: Inversions

Settings

Saving...
Server Error
Resubmit