6.Sorting§

Each record contains a field called the key.
- Linear order: comparison.
Measures of cost:
- Comparisons
- Swaps

Insertion Sort

1 / 11 Settings

<<<>>>

Insertion Sort starts with the record in position 1.

Saving...

Server Error
Resubmit

Analysis: Worst Case

1 / 24 Settings

<<<>>>

We first examine the worst case cost.

Saving...

Server Error
Resubmit

Analysis: Best Case

1 / 5 Settings

<<<>>>

Now we will consider the best case cost.

Saving...

Server Error
Resubmit

Analysis: Average Case

1 / 8 Settings

<<<>>>

Finally, consider the average case cost.

Saving...

Server Error
Resubmit

Bubble Sort

1 / 13 Settings

<<<>>>

Moving from left to right, compare adjacent elements and swap if the left one is bigger than the right one.

Saving...

Server Error
Resubmit

1 / 10 Settings

<<<>>>

Moving from left to right, compare adjacent elements and swap if the left one is bigger than the right one.

Saving...

Server Error
Resubmit

Analysis

1 / 24 Settings

<<<>>>

What is the cost of Bubblesort?

Saving...

Server Error
Resubmit

Selection Sort

1 / 15 Settings

<<<>>>

Moving from left to right, find the element with the greatest value.

Saving...

Server Error
Resubmit

1 / 13 Settings

<<<>>>

Second pass: moving from left to right, find the element with the second greatest value.

Saving...

Server Error
Resubmit

Analysis

1 / 40 Settings

<<<>>>

What is the cost for Selection Sort?

Saving...

Server Error
Resubmit

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?

1 / 16 Settings

<<<>>>

What is the average number of inversions?

Saving...

Server Error
Resubmit