CSC1120 - Sorting

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:
    <table>
      <tr>
        <td>S</td>
        <td>O</td>
        <td>R</td>
        <td>T</td>
        <td>I</td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>
    --

* Select smallest element
    <table>
      <tr>
        <td>S</td>
        <td>O</td>
        <td>R</td>
        <td>T</td>
        <td>I</td>
        <td>N</td>
        <td style="background: #600;">G</td>
      </tr>
    </table>
    --

* Swap with first element in unsorted
    <table>
      <tr>
        <td style="background: #600;">G</td>
        <td>O</td>
        <td>R</td>
        <td>T</td>
        <td>I</td>
        <td>N</td>
        <td>S</td>
      </tr>
    </table>
    --

* Split index is now 1
    <table>
      <tr>
        <td style="background: #600;">G</td>
        <td style="background: #fff;"></td>
        <td>O</td>
        <td>R</td>
        <td>T</td>
        <td>I</td>
        <td>N</td>
        <td>S</td>
      </tr>
    </table>
    --

* Select smallest element in unsorted
    <table>
      <tr>
        <td style="background: #600;">G</td>
        <td style="background: #fff;"></td>
        <td>O</td>
        <td>R</td>
        <td>T</td>
        <td style="background: #600;">I</td>
        <td>N</td>
        <td>S</td>
      </tr>
    </table>

---
    * From previous slide
    <table>
      <tr>
        <td style="background: #600;">G</td>
        <td style="background: #fff;"></td>
        <td>O</td>
        <td>R</td>
        <td>T</td>
        <td style="background: #600;">I</td>
        <td>N</td>
        <td>S</td>
      </tr>
    </table>
    --

* Swap and grow sorted portion
    <table>
      <tr>
        <td style="background: #600;">G</td>
        <td style="background: #600;">I</td>
        <td style="background: #fff;"></td>
        <td>R</td>
        <td>T</td>
        <td>O</td>
        <td>N</td>
        <td>S</td>
      </tr>
    </table>
    --

* Repeat
    <table>
      <tr>
        <td style="background: #600;">G</td>
        <td style="background: #600;">I</td>
        <td style="background: #fff;"></td>
        <td>R</td>
        <td>T</td>
        <td>O</td>
        <td style="background: #600;">N</td>
        <td>S</td>
      </tr>
    </table>
    --

<table>
      <tr>
        <td style="background: #600;">G</td>
        <td style="background: #600;">I</td>
        <td style="background: #600;">N</td>
        <td style="background: #fff;"></td>
        <td>T</td>
        <td>O</td>
        <td>R</td>
        <td>S</td>
      </tr>
    </table>
    --

---
    <table>
      <tr>
        <td style="background: #600;">G</td>
        <td style="background: #600;">I</td>
        <td style="background: #600;">N</td>
        <td style="background: #fff;"></td>
        <td>T</td>
        <td style="background: #600;">O</td>
        <td>R</td>
        <td>S</td>
      </tr>
    </table>
    --

<table>
      <tr>
        <td style="background: #600;">G</td>
        <td style="background: #600;">I</td>
        <td style="background: #600;">N</td>
        <td style="background: #600;">O</td>
        <td style="background: #fff;"></td>
        <td>T</td>
        <td>R</td>
        <td>S</td>
      </tr>
    </table>
    --

<table>
      <tr>
        <td style="background: #600;">G</td>
        <td style="background: #600;">I</td>
        <td style="background: #600;">N</td>
        <td style="background: #600;">O</td>
        <td style="background: #fff;"></td>
        <td>T</td>
        <td style="background: #600;">R</td>
        <td>S</td>
      </tr>
    </table>
    --

<table>
      <tr>
        <td style="background: #600;">G</td>
        <td style="background: #600;">I</td>
        <td style="background: #600;">N</td>
        <td style="background: #600;">O</td>
        <td style="background: #600;">R</td>
        <td style="background: #fff;"></td>
        <td>T</td>
        <td>S</td>
      </tr>
    </table>
    --

<table>
      <tr>
        <td style="background: #600;">G</td>
        <td style="background: #600;">I</td>
        <td style="background: #600;">N</td>
        <td style="background: #600;">O</td>
        <td style="background: #600;">R</td>
        <td style="background: #fff;"></td>
        <td>T</td>
        <td style="background: #600;">S</td>
      </tr>
    </table>
    --

<table>
      <tr>
        <td style="background: #600;">G</td>
        <td style="background: #600;">I</td>
        <td style="background: #600;">N</td>
        <td style="background: #600;">O</td>
        <td style="background: #600;">R</td>
        <td style="background: #600;">S</td>
        <td style="background: #fff;"></td>
        <td>T</td>
      </tr>
    </table>
    --

---
    # 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
    <table>
      <tr>
        <td>S</td>
        <td>O</td>
        <td>R</td>
        <td>T</td>
        <td>I</td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>
    --

* Increment split index, **S** is sorted
    <table>
      <tr>
        <td style="background: #600;">S</td>
        <td style="background: #fff;"></td>
        <td>O</td>
        <td>R</td>
        <td>T</td>
        <td>I</td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>
    --

* Increment split index again
    <table>
      <tr>
        <td style="background: #600;">S</td>
        <td>O</td>
        <td style="background: #fff;"></td>
        <td>R</td>
        <td>T</td>
        <td>I</td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>
    --

* Swap **S** with **O*>
    <table>
      <tr>
        <td>O</td>
        <td style="background: #600;">S</td>
        <td style="background: #fff;"></td>
        <td>R</td>
        <td>T</td>
        <td>I</td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>
    --

* Sorted portion now sorted
    <table>
      <tr>
        <td style="background: #600;">O</td>
        <td style="background: #600;">S</td>
        <td style="background: #fff;"></td>
        <td>R</td>
        <td>T</td>
        <td>I</td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>
    --

* Increment split index again
    <table>
      <tr>
        <td style="background: #600;">O</td>
        <td style="background: #600;">S</td>
        <td>R</td>
        <td style="background: #fff;"></td>
        <td>T</td>
        <td>I</td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>

---
    * From previous slide
    <table>
      <tr>
        <td style="background: #600;">O</td>
        <td style="background: #600;">S</td>
        <td>R</td>
        <td style="background: #fff;"></td>
        <td>T</td>
        <td>I</td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>
    --

* Swap **R** with **S**
    <table>
      <tr>
        <td style="background: #600;">O</td>
        <td>R</td>
        <td style="background: #600;">S</td>
        <td style="background: #fff;"></td>
        <td>T</td>
        <td>I</td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>
    --

* No need to swap **R** with **O**, so sorted
    <table>
      <tr>
        <td style="background: #600;">O</td>
        <td style="background: #600;">R</td>
        <td style="background: #600;">S</td>
        <td style="background: #fff;"></td>
        <td>T</td>
        <td>I</td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>
    --

* Increment split index again
    <table>
      <tr>
        <td style="background: #600;">O</td>
        <td style="background: #600;">R</td>
        <td style="background: #600;">S</td>
        <td>T</td>
        <td style="background: #fff;"></td>
        <td>I</td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>
    --

* No swaps needed
    <table>
      <tr>
        <td style="background: #600;">O</td>
        <td style="background: #600;">R</td>
        <td style="background: #600;">S</td>
        <td style="background: #600;">T</td>
        <td style="background: #fff;"></td>
        <td>I</td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>

---
    * From previous slide
    <table>
      <tr>
        <td style="background: #600;">O</td>
        <td style="background: #600;">R</td>
        <td style="background: #600;">S</td>
        <td style="background: #600;">T</td>
        <td style="background: #fff;"></td>
        <td>I</td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>
    --

* Increment split index again
    <table>
      <tr>
        <td style="background: #600;">O</td>
        <td style="background: #600;">R</td>
        <td style="background: #600;">S</td>
        <td style="background: #600;">T</td>
        <td>I</td>
        <td style="background: #fff;"></td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>
    --

* Swap **I** with **T**
    <table>
      <tr>
        <td style="background: #600;">O</td>
        <td style="background: #600;">R</td>
        <td style="background: #600;">S</td>
        <td>I</td>
        <td style="background: #600;">T</td>
        <td style="background: #fff;"></td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>
    --

* Swap **I** with **S**
    <table>
      <tr>
        <td style="background: #600;">O</td>
        <td style="background: #600;">R</td>
        <td>I</td>
        <td style="background: #600;">S</td>
        <td style="background: #600;">T</td>
        <td style="background: #fff;"></td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>
    --

* Swap **I** with **R**
    <table>
      <tr>
        <td style="background: #600;">O</td>
        <td>I</td>
        <td style="background: #600;">R</td>
        <td style="background: #600;">S</td>
        <td style="background: #600;">T</td>
        <td style="background: #fff;"></td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>
    --

* Swap **I** with **O**
    <table>
      <tr>
        <td>I</td>
        <td style="background: #600;">O</td>
        <td style="background: #600;">R</td>
        <td style="background: #600;">S</td>
        <td style="background: #600;">T</td>
        <td style="background: #fff;"></td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>

---
    * Sort order restored
    <table>
      <tr>
        <td style="background: #600;">I</td>
        <td style="background: #600;">O</td>
        <td style="background: #600;">R</td>
        <td style="background: #600;">S</td>
        <td style="background: #600;">T</td>
        <td style="background: #fff;"></td>
        <td>N</td>
        <td>G</td>
      </tr>
    </table>
    --

* Increment split index again
    <table>
      <tr>
        <td style="background: #600;">I</td>
        <td style="background: #600;">O</td>
        <td style="background: #600;">R</td>
        <td style="background: #600;">S</td>
        <td style="background: #600;">T</td>
        <td>N</td>
        <td style="background: #fff;"></td>
        <td>G</td>
      </tr>
    </table>
    --

* Swap **N** with **T**, then **S**, then **R**, then **O**
    <table>
      <tr>
        <td style="background: #600;">I</td>
        <td>N</td>
        <td style="background: #600;">O</td>
        <td style="background: #600;">R</td>
        <td style="background: #600;">S</td>
        <td style="background: #600;">T</td>
        <td style="background: #fff;"></td>
        <td>G</td>
      </tr>
    </table>
    --

* Sort order restored
    <table>
      <tr>
        <td style="background: #600;">I</td>
        <td style="background: #600;">N</td>
        <td style="background: #600;">O</td>
        <td style="background: #600;">R</td>
        <td style="background: #600;">S</td>
        <td style="background: #600;">T</td>
        <td style="background: #fff;"></td>
        <td>G</td>
      </tr>
    </table>
    --

* Increment split index again
    <table>
      <tr>
        <td style="background: #600;">I</td>
        <td style="background: #600;">N</td>
        <td style="background: #600;">O</td>
        <td style="background: #600;">R</td>
        <td style="background: #600;">S</td>
        <td style="background: #600;">T</td>
        <td>G</td>
      </tr>
    </table>
    --

* Swap **G** with **T**, then **S**, then **R**, then **O**, then **N**, then **I**
    <table>
      <tr>
        <td>G</td>
        <td style="background: #600;">I</td>
        <td style="background: #600;">N</td>
        <td style="background: #600;">O</td>
        <td style="background: #600;">R</td>
        <td style="background: #600;">S</td>
        <td style="background: #600;">T</td>
      </tr>
    </table>
    --

* All done