Discussion 13: More Sorting Christine Zhou Agenda Announcements (Probably only 2 of these) Quicksort Review Problem 1 Stability Review Problem 2 Radix Sorts Problem 3 Announcements Practice Mock Final: Tuesday 5/7 in Dwinelle 155, from 7-10PM Project 3 Phase 1 is due Friday at 11:59pm! Office hours Remember the policies Only 1 more discussion section!! Discussion survey: tinyurl.com/cz-disc13-sp19 Quicksort Algorithm: Pick a pivot, partition elements based on the pivot, repeat on partitions as long as they include more than one element, then combine partitions How to pick a pivot? How to partition? Always pick the leftmost/rightmost element Randomly pick an element Three way merge: split into the less than, equal, and greater than partition (auxiliary arrays) Hoare: split into less than or equal to and greater than partition (in place) Runtime: (which part of the algorithm most heavily influences the runtime?) Pivot choice! 1 Quicksort Sort the following unordered list using stable quicksort. Assume that the pivot you use is always the first element and that we use the 3-way merge partitioning process described in lecture and lab last week. Show the steps taken at each partitioning step. 18, 7, 22, 34, 99, 18, 11, 4 1 Quicksort 18-, 7, 22, 34, 99, 18, 11, 4 (18 is the pivot) 7-, 11, 4 | 18, 18 | 22, 34, 99 (7 is the pivot) 4, 7, 11, 18, 18 | -22-, 34, 99 (22 is the pivot) 4, 7, 11, 18, 18, 22 | -34-, 99 (34 is the pivot) 4, 7, 11, 18, 18, 22, 34, 99 1 Quicksort What is the best and worst case running time of Quicksort with Hoare Partitioning on N elements? Give an example of a list of 5 numbers that would result in best and worst case running time. Best: Theta(N log N) Example: 3 1 2 5 4 Worst: Theta(N^2) Example: 1 3 3 4 5 (if the first or last element is picked as the pivot) 1 Quicksort What are two techniques that can be used to reduce the probability of Quicksort taking the worst case running time? 1. Randomly ch