name: inverse layout: true class: taylor msoe --- class: center, middle .title[ # Sorting ## Selection Sort and Insertion Sort ] ??? Toggle speaker view by pressing P Pressing C clones the slideshow view, which is the view to put on the projector if you're using speaker view. Press ? to toggle keyboard commands help. --- # Sorting * Fundamental computer science problem -- * Suprising large number of ways to sort --- # Selection Sort * Start with an unsorted array of length $n$ -- * Partition the array into a sorted portion and an unsorted portion begin with a **split index** of $0$ -- * (all elements in the unsorted portion) -- * Select smallest value in the unsorted portion -- * Swap it with the first element in the unsorted portion -- * Increment **split index** -- * (sorted portion gains and element, unsorted portion loses an element) --- * Starting array:
S
O
R
T
I
N
G
-- * Select smallest element
S
O
R
T
I
N
G
-- * Swap with first element in unsorted
G
O
R
T
I
N
S
-- * Split index is now 1
G
O
R
T
I
N
S
-- * Select smallest element in unsorted
G
O
R
T
I
N
S
--- * From previous slide
G
O
R
T
I
N
S
-- * Swap and grow sorted portion
G
I
R
T
O
N
S
-- * Repeat
G
I
R
T
O
N
S
--
G
I
N
T
O
R
S
--
G
I
N
T
O
R
S
---
G
I
N
T
O
R
S
--
G
I
N
O
T
R
S
--
G
I
N
O
T
R
S
--
G
I
N
O
R
T
S
--
G
I
N
O
R
T
S
--
G
I
N
O
R
S
T
--
G
I
N
O
R
S
T
--- # Time complexity * What is the worst-case time complexity? -- * $O(n^2)$ -- * What is the best-case time complexity? -- * $O(n^2)$ --- class: animated fadeIn # Insertion Sort * Start with an unsorted array of length $n$ -- * Partition the array into a sorted portion and an unsorted portion begin with a **split index** of $0$ -- * (all elements in the unsorted portion) -- * Select first value in the unsorted portion -- * Compare with the largest element in the sorted portion -- * Keep swapping in the sorted portion until sorted portion is sorted -- * (sorted portion gains and element, unsorted portion loses an element) --- * Starting array with split index at zero
S
O
R
T
I
N
G
-- * Increment split index, **S** is sorted
S
O
R
T
I
N
G
-- * Increment split index again
S
O
R
T
I
N
G
-- * Swap **S** with **O*>
O
S
R
T
I
N
G
-- * Sorted portion now sorted
O
S
R
T
I
N
G
-- * Increment split index again
O
S
R
T
I
N
G
--- * From previous slide
O
S
R
T
I
N
G
-- * Swap **R** with **S**
O
R
S
T
I
N
G
-- * No need to swap **R** with **O**, so sorted
O
R
S
T
I
N
G
-- * Increment split index again
O
R
S
T
I
N
G
-- * No swaps needed
O
R
S
T
I
N
G
--- * From previous slide
O
R
S
T
I
N
G
-- * Increment split index again
O
R
S
T
I
N
G
-- * Swap **I** with **T**
O
R
S
I
T
N
G
-- * Swap **I** with **S**
O
R
I
S
T
N
G
-- * Swap **I** with **R**
O
I
R
S
T
N
G
-- * Swap **I** with **O**
I
O
R
S
T
N
G
--- * Sort order restored
I
O
R
S
T
N
G
-- * Increment split index again
I
O
R
S
T
N
G
-- * Swap **N** with **T**, then **S**, then **R**, then **O**
I
N
O
R
S
T
G
-- * Sort order restored
I
N
O
R
S
T
G
-- * Increment split index again
I
N
O
R
S
T
G
-- * Swap **G** with **T**, then **S**, then **R**, then **O**, then **N**, then **I**
G
I
N
O
R
S
T
-- * All done