6.Sorting§

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.

Initial Step

Consider this start to the process.

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Analysis: Worst Case

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Analysis: Best Case

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Analysis: Average Case

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Bubble Sort

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Analysis

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Selection Sort

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Analysis

Settings

Proficient Saving... Error 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 (1)

Exchange Sorting

Settings

Proficient Saving... Error Saving
Server Error
Resubmit