Discussion 10: Sorting Christine Zhou Agenda Announcements We’ll try to get through all the worksheet, but no guarantees Announcements Midterm 2 is tomorrow! Check room assignments HW6 due Friday Project 2 milestone due on Monday, just need to pass the integration tests Best of luck!! No slip hours for this! You do not need your game fully functioning, remember these integration tests are not comprehensive! Extra office hours Monday and Wednesday night! 6-8PM More details to come later Insertion Sort Have a sorted portion and a non-sorted portion In the non-sorted portion, pick the first element and “insert” its correct position Keeping swapping with whatever is to the left Will be at the right position when the left element is less than the element you are inserting Selection Sort Scan through the array, always “selecting” the smallest item and bringing it to the front Merge Sort 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 halves together Have pointers to each partitions and combine them so the partitions are now sorted Heapsort Use a max heap Algorithm: Turn elements into a heap, represent with an array Repeat: remove max and rearrange heap, put max at the end Quicksort Pick a pivot Divide array into 3 parts: less than portion, equal to portion, greater than portion Repeat previous steps on 1st and 3rd if they include more than one element Runtime: Average case: 𝚹(NlogN) Worst case: 𝚹(N^2) Counting Sort Keep an array called counts that keeps track of the count of each value, go through the entire array and collect the counts Keep an array called starts and this will tell us where to start for each element, go through the counts and collect the starts Go through all the elements of the array and place the element where it should belong based on the starts array Runtime: N is the nu