Discussion 12: ADT's & Sorting Christine Zhou Agenda Announcements Review sorts and runtimes Problem 1 Review ADT’s Problem 2.1 Announcements Project 2C is due today at 11:59pm! Apologies for the AG confusion :( Office hours We’re sorry OH has been so busy :( Remember the policies Midterm 2 grades have been released! Regrades due this Friday Let me know if you want to chat! Only 2 more discussion sections!! Discussion survey: tinyurl.com/cz-disc12-sp19 Forewarning Time for a lot of algorithms... Insertion Sort Maintain a sorted portion and an unsorted portion Algorithm: Pick the first element in the unsorted portion and insert it into the correct position in the sorted portion Keeping swapping the item with whatever is to the left Will be at the correct position when the left element is less than the element we are inserting Based on the idea of inversions Two elements that are out of order (ex. [1, 2, 4, 3] has one inversion between 4 and 3) Every swap decreases the number of inversions by 1 Runtime: Think about this in terms of inversions Best: 𝝧(N) If there are no inversions Worst:𝝧(N^2) If there are maximum number of inversions Selection Sort Maintain a sorted portion and an unsorted portion Algorithm: Iterate through the unsorted portion and select the smallest item, bring it to the end of the sorted portion Runtime: Best: 𝝧(N^2) Worst: 𝝧(N^2) Merge Sort Split up the work, a single item by itself is inherently sorted Algorithm: Split array into two equal partitions Call mergesort on each of the partitions Now the partitions are sorted or the partitions are one element Merge the two partitions together Have pointers to each partition and combine them so the partitions are now sorted Runtime: Best: 𝝧(N log N) Worst: 𝝧(N log N) 1 Mechanical Sorting Show the steps taken by each sort on the following unordered list 0, 4, 2, 7, 6, 1, 3, 5 a) Insertion sort b) Selection sort c) Merge sort