CSC1120 - More Sorting

name: inverse
    layout: true
    class: taylor msoe
    ---
    class: center, middle

.title[
      # More Sorting
      ## Shell Sort and Merge 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.

---
    # Insertion Sort revisited

* Insertion Sort performance:
    --

* Best case: $O(n)$
    --
        * Worst case: $O(n^2)$
    --
    * How could we improve this?
    --

* Have more work when we need to do lots of swaps
    --

* Could we use binary search to figure out where insert the item in the sorted portion?
    --

* Doesn't help, since we still need to shift all elements to make room for item
    --

---
    * Let's look at the number of swaps needed for this example:
    <table>
      <tr>
        <td>2</td>
        <td>3</td>
        <td>8</td>
        <td>5</td>
        <td>6</td>
        <td>1</td>
      </tr>
    </table>
    --

* First three sorted with no swaps
    <table>
      <tr>
        <td style="background: #600;">2</td>
        <td style="background: #600;">3</td>
        <td style="background: #600;">8</td>
        <td>5</td>
        <td style="background: #fff;"></td>
        <td>6</td>
        <td>1</td>
      </tr>
    </table>
    --

* Swap **5** with **8** (Total swaps: 1)
    <table>
      <tr>
        <td style="background: #600;">2</td>
        <td style="background: #600;">3</td>
        <td style="background: #600;">5</td>
        <td style="background: #600;">8</td>
        <td style="background: #fff;"></td>
        <td>6</td>
        <td>1</td>
      </tr>
    </table>
    --

* Swap **6** with **8** (Total swaps: 2)
    <table>
      <tr>
        <td style="background: #600;">2</td>
        <td style="background: #600;">3</td>
        <td style="background: #600;">5</td>
        <td style="background: #600;">6</td>
        <td style="background: #600;">8</td>
        <td style="background: #fff;"></td>
        <td>1</td>
      </tr>
    </table>
    --

* Swap **1** with everything (Total swaps: 7)
    <table>
      <tr>
        <td style="background: #600;">1</td>
        <td style="background: #600;">2</td>
        <td style="background: #600;">3</td>
        <td style="background: #600;">5</td>
        <td style="background: #600;">6</td>
        <td style="background: #600;">8</td>
      </tr>
    </table>

---
    * How could we reduce swaps?
    <table>
      <tr>
        <td>2</td>
        <td>3</td>
        <td>8</td>
        <td>5</td>
        <td>6</td>
        <td>1</td>
      </tr>
    </table>
    --

* First swap **1** with **8** (Total swaps: 1)
    <table>
      <tr>
        <td style="background: #600;">2</td>
        <td style="background: #600;">3</td>
        <td>1</td>
        <td style="background: #fff;"></td>
        <td>5</td>
        <td>6</td>
        <td>8</td>
      </tr>
    </table>
    --

* Swap **1** with **3**, then **2** (Total swaps: 3)
    <table>
      <tr>
        <td style="background: #600;">1</td>
        <td style="background: #600;">2</td>
        <td style="background: #600;">3</td>
        <td style="background: #fff;"></td>
        <td>5</td>
        <td>6</td>
        <td>8</td>
      </tr>
    </table>
    --

* No more swaps needed (3 instead of 7 swaps)
    <table>
      <tr>
        <td style="background: #600;">1</td>
        <td style="background: #600;">2</td>
        <td style="background: #600;">3</td>
        <td style="background: #600;">5</td>
        <td style="background: #600;">6</td>
        <td style="background: #600;">8</td>
      </tr>
    </table>
    --

* Whenever we can swap with a big gap, it has the potential to save big

---
    # Shell Sort

* Uses the concept of a **gap** to improve performance
    --

* The size of the gap is not defined as part of Shell Sort
    --

* Dr. Shell originally proposed $\lfloor \frac{N}{2^k} \rfloor$ as the gap size

---
    * 8 elements, so gap is 4 (= 8/2)

<table>
      <tr>
        <td style="color: #fff">S</td>
        <td style="color: #ccc">O</td>
        <td style="color: #aaa">R</td>
        <td style="color: #777">T</td>
        <td style="color: #fff">I</td>
        <td style="color: #ccc">N</td>
        <td style="color: #aaa">G</td>
        <td style="color: #777">S</td>
      </tr>
    </table>
    --

---
    * Swap **I** with **S**, **N** with **O**, **G** with **R**, and **S** with **T**
    <table>
      <tr>
        <td style="color: #fff">I</td>
        <td style="color: #ccc">N</td>
        <td style="color: #aaa">G</td>
        <td style="color: #777">S</td>
        <td style="color: #fff">S</td>
        <td style="color: #ccc">O</td>
        <td style="color: #aaa">R</td>
        <td style="color: #777">T</td>
      </tr>
    </table>
    --

* Now make use a gap of 2

---
    * Now make the gap 1 (traditional Insertion Sort)
    <table>
      <tr>
        <td style="background: #600;">I</td>
        <td style="background: #600;">N</td>
        <td>G</td>
        <td style="background: #fff;"></td>
        <td>O</td>
        <td>R</td>
        <td>S</td>
        <td>S</td>
        <td>T</td>
      </tr>
    </table>
    --

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

* No more swaps needed
    <table>
      <tr>
        <td style="background: #600;">I</td>
        <td style="background: #600;">G</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;">S</td>
        <td style="background: #600;">T</td>
      </tr>
    </table>

---
    # Merge Sort

* A _divide and conquer_ algorithm typically implemented with recursion
    --

* Recursively split the array into two smaller arrays
    --

* Base case: arrays of length one (already sorted)
    --

* Progressively merge pairs of arrays back together maintaining sorted order