class: center, middle # Sorting --- name: agenda ## Agenda .two-columns[ - [Agenda](#agenda) - [Sorting Motivation](#sorting-motivation) - [Bubble Sort](#bubble-sort) - [Selection Sort](#selection-sort) - [Stable Sorting](#stable-sorting) - [Insertion Sort](#insertion-sort) - [MergeSort](#mergesort) - [QuickSort](#quicksort) - [Resources](#resources) ] --- name: sorting-motivation ## Sorting Motivation There are many use cases for sorting things, it's something you most likely do every day, it's also something your computer does every day, all the time. Can you think of common things that your computer sorts for you? -- - Emails - Articles - Contacts in your Phone - Your calendar events -- The question is, how is your computer sorting so many thing so quickly? --- name: bubble-sort class: middle ## Bubble Sort --- ### Bubble Sort: Introduction What if we simply walk through the list, and repeatedly swap out-of-order elements? -- Let's start with the array: `[5, 2, 4, 3, 1]` -- We begin by starting with `5` and `2`, which are swapped: `[2, 5, 4, 3, 1]` -- Then `5` and `4` must be swapped: `[2, 4, 5, 3, 1]` -- Now `5` and `3` are out of order: `[2, 4, 3, 5, 1]`. -- Finally for this pass, we must fix `5` and `1`: `[2, 4, 3, 1, 5]` -- We must then repeat this process until the entire list is sorted. -- How much work is required if the list is sorted? Reversed? --- ### Bubble Sort: Implementation .pull-left[ ### A helpful animation <img src="images/sort_bubble.gif" width="350" height="200"> ### Pseudocode ``` While the array is not sorted: For each element in the array (except the last): If the current element is greater than the next element: Swap the current and next element. ``` ] .pull-right[ ### Details - Comparison based sort - Extremely simple - Stable: Does not change the relative order of elements of equal value - Adaptive: Runs in linear time on sorted arrays - Larger elements "bubble" to the top - Too slow for practical use ] --- name: selection-sort class: middle ## Selection Sort --- ### Selection Sort: Introduction What if we simply selected the minimum from the array at each pass, and appended it to a sorted sublist? -- Let's start with the array: `[5, 2, 4, 3, 1]`, and the sorted sublist `[]` -- Select the smallest element in the list, and append it to the sorted list. `[2, 4, 3, 5]`, `[1]` -- We repeat this process, until the unsorted array is empty: `[4, 3, 5]`, `[1, 2]` -- `[4, 5]`, `[1, 2, 3]` -- `[5]`, `[1, 2, 3, 4]` -- `[]`, `[1, 2, 3, 4, 5]` -- Although this will work, ideally we would make this work in-place, like bubble sort did. -- We can accomplish this by using swaps, and using the left side of our array as our sorted portion. --- ### Selection Sort: In-Place We start with the same array: `[|5, 2, 4, 3, 1]` where the bar denotes the sorted sublist. -- For each index in the array, from left to right, we select the minimum value in the array, and swap it with our current position. -- `[1|, 2, 4, 3, 5]` Here we selected the `1`, and swapped it with the `5`. -- `[1, 2|, 4, 3, 5]` Here we selected the `2`, and swapped it with itself. -- `[1, 2, 3|, 4, 5]` On this step, we swapped the `3` and the `4`. -- `[1, 2, 3, 4|, 5]` On this step, we swapped the `4` with itself. -- And finally, we can swap the `5` with itself, but do we actually have to do this? -- No, the final element must be the largest, this algorithm can exit safely after evaluating the second to last index. -- How much work is required for Selection Sort on an already sorted list? Reversed list? --- ### Selection Sort: Implementation .pull-left[ #### A helpful animation <img src="images/sort_selection.gif" width="400" height="170"> #### Pseudocode ``` For each i from 0 to n: Set the current minimum index to i For each j from i + 1 to n: If the element at j is less than the element at the current minimum index: Set the current minimum index to j Swap the elements at i and the current minimum index ``` ] .pull-right[ #### Details - Starts from the left, selects the minimum element in the array and swaps the value at it's current position with the minimum - Unstable: Elements relative orders are not preserved, though it can be made stable - Linear in regards to swaps, which is unique ] --- ### Selection Sort: Analysis - Worst Case: $O(n^2)$ - Average Case: $O(n^2)$ - Best Case: $O(n^2)$ Selection sort scans the array at each interval searching for the minimum, the total number of comparisons is: $$(n - 1) + (n - 2) + (n - 3) + ... + 1 = \sum_{i = 1}^{n - 1} i$$ Which evaluates to $O(n^2)$ in all cases. --- name: stable-sorting class: middle ## Stable Sorting --- ### Stable Sorting: Overview If we want equal elements to preserve their order in the original list, we must use a stable sorting algorithm. Consider if we wanted to sort a list by multiple keys, when we sort by the secondary key, we do not want the primary order to be disrupted! .pull-left[ <img src="images/sort_stable.png" width="200" height="350"> ] Let's examine how stable sorting could impact the order of these cards. We can see that stable sorting preserves the *relative* order of the cards of rank 5. Can you think of some applications where this may be important? -- How about flights? They could be sorted by price, then by day, in which case we do not want our list to be out of order by price! --- name: insertion-sort class: middle ## Insertion Sort --- ### Insertion Sort: Introduction What if we *inserted* each element in the array into an already sorted array? -- Similarly to Selection Sort, we can use the left side of the array to hold the *sorted* elements, and iterate through to the right. -- Let's start with the array: `[5|, 2, 4, 3, 1]` Where the `|` marks the end of the sorted sublist. -- `[2, 5|, 4, 3, 1]` The `2` element gets inserted into the sorted sublist. -- `[2, 4, 5|, 3, 1]` Then the `4` gets inserted. -- `[2, 3, 4, 5|, 1]` After the `3` is inserted. -- Finally, the `1` gets inserted and we have concluded our sort: `[1, 2, 3, 4, 5]` -- How much work is required if the list is reversed? Already sorted? Partially Sorted? --- ### Insertion Sort: Implementation .pull-left[ #### A helpful animation <img src="images/sort_insertion.gif" width="350" height="200"> #### Pseudocode ``` For each i from 0 to n: For each j from i to 0: If the element at j-1 is greater than the element at j: Swap the elements at j-1 and j Otherwise: Break ``` ] .pull-right[ #### Details - The left-hand side of the array is considered sorted, the algorithm then *inserts* each new element into it's proper place - Stable: The order of elements of equal value is preserved - Adaptive: Efficient for datasets that are already sorted or partially sorted - Efficient on small datasets - In-place: Requires a constant amount of extra memory ] --- ### Insertion Sort: Analysis - Worst Case: $O(n^2)$ - Average Case: $O(n^2)$ - Best Case: $O(n)$ - Partially Sorted Arrays: $O(kn)$ where $k$ is some constant limit on the number of inversions. Consider the act of inserting an element into a sorted sublist, if the element is the smallest element in the list, it must be swapped all the way to the beginning of the list. The worst case for insertion sort is when the list is in reversed order, forcing the algorithm to make $1 + 2 + 3 + ... + n - 1$ swaps. We can convert this statement into a recurrence, which can then be used to attain the closed-form solution: $$\sum_{i = 1}^{n - 1} i = \frac{n(n - 1)}{2} = O(n^2)$$ --- name: mergesort class: middle ## MergeSort --- ### MergeSort: Introduction What if we could sort an array recursively and efficiently in any case? - What should our base case be? - How can we get there? - How do we put together the pieces? -- As the name may suggest, we are going to put the pieces back together by *merging* them, but wait - what pieces? -- MergeSort works by breaking down an array into singletons, arrays of length 1 or 0, then recombines them via merging. -- Starting with the array below, we split down to singletons. `[5, 2, 4, 3, 1]` -- `[[5, 2, 4], [3, 1]]` -- `[[[5, 2], [4]], [[3], [1]]]` -- `[[[[5], [2]], [4]], [[3], [1]]]` --- ### MergeSort: Introduction (cont) Starting with our singletons from the last slide: `[[[[5], [2]], [4]], [[3], [1]]]` We now merge these pieces back together. -- `[[[2, 5], [4]], [1, 3]]` -- `[[2, 4, 5], [1, 3]]` -- `[1, 2, 3, 4, 5]` And we are done! -- While you are implementing this algorithm strongly consider what it's runtime should be. --- ### MergeSort: Implementation .pull-left[ #### A helpful animation <img src="images/sort_merge.gif" width="300" height="200"> #### Pseudocode for MergeSort ``` Let Array be an array of n elements. if the number of elements is greater than 1: call mergesort on the first half call mergesort on the second half merge the array ``` ] .pull-right[ #### Pseudocode for Merge ``` Let Array be an array of n elements. Temp = Copy(Array) Let j = 0, k = MiddleIndex(Array) For each i from 0 to n: If j >= MiddleIndex(Array): Array[i] = Temp[k], k = k + 1 Else if (k >= n): Array[i] = Temp[j], j = j + 1 Else if Temp[j] < Temp[k]: Array[i] = Temp[j], j = j + 1 Else: Array[i] = Temp[k], k = k + 1 ``` #### Details - Recursive: Calls itself to solve the problem - Stable: Relative orderings of elements of equal value are preserved. - Not Adaptive: Takes the same amount of time in all conditions ] --- ### MergeSort: Analysis MergeSort calls itself on two halves of the original list, then combines them. Roughly speaking, we can provide this recursive definition: `MergeSort(n) = Merge(MergeSort(n / 2), MergeSort(n / 2))` -- We can translate this into the recurrence: $$ T(n) = 2T(n / 2) + n = O(n \log n) $$ To solve this recurrence you can unroll the equation, use the [tree method](https://www.educative.io/collection/page/10370001/760001/1280004), or the master method. --- name: quicksort class: middle ## QuickSort --- ### QuickSort: Introduction What if instead of simply dividing the array into two halves, we split it into lower and upper portions, then sorted those halves? We'll walk through our normal example with this scheme: `[5, 2, 4, 3, 1]` Starting with our array, we pick a *pivot*, which is normally the first, last, middle, or median of 3 elements. For this example, we will pick the first element. -- `[2, 4, 3, 1], [5], []` After pivoting on 5. -- `[1], [2], [4, 3], [5], []` Pivoting on 2. -- `[1], [2], [3], [4], [], [5], []` Pivoting on 4. -- `[1, 2, 3, 4, 5]` Combing the results. -- Of course, this is actually done in-place, with recursive calls on each sublist. --- ### QuickSort Implementation .pull-left[ #### A helpful animation <img src="images/sort_quick.gif" width="400" height="200"> #### Pseudocode for Partition ``` set i to lo + 1 and j to hi while true: increment i until array at i is greater than array at lo decrement j until array at j is less than array at lo break if j <= i swap the elements at i and at j swap the elements at lo and at j return j ``` ] .pull-right[ #### Pseudocode for QuickSort ``` if lo is less than hi: p = call partition on the array call quicksort with lo and p - 1 call quicksort with p + 1 and hi ``` #### Details - Think of some details as you work! We'll do this section together ] --- ### QuickSort: Analysis #### Worst Case The partition is always the largest or smallest, removing only a single element from each call. $$T(n) = n + T(n - 1) = \sum_{i=1}^n i = O(n^2)$$ #### Best Case We can look at the best case in two different ways, as a recurrence relation $$ T(n) = n + 2T \bigg( \frac{n}{2} \bigg) = k \cdot n + 2^k T \bigg(\frac{n}{2^k} \bigg) = n \cdot \log n + n = O(n \cdot \log n) $$ Or, as a call tree, where each level of the tree examines all $n$ elements, and the max height of this tree is $\log n$, since we dividing $n$ by $2$ at each call, which equates to $O(n \cdot \log n)$ --- name: resources ## Resources Visualizations - [sorting.at](http://sorting.at/) - [Comparison Sorts TOPTAL](https://www.toptal.com/developers/sorting-algorithms) - [Sound of Sorting](https://www.youtube.com/watch?v=kPRA0W1kECg) - [Comparison Sorts USFCA](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html) - [Median of Medians](http://eshrews.com/select)