Welcome to Lesson 19!AnnouncementsProject Report 5 due todayLab 10 due ThursdayReturn QuizzesPractice quiz only on Thursday due to time constraintsProject PresentationsTeams 1, 8, 7, 2 todayFinal Exam one week from todayComprehensiveSimilar in format to midtermsFinal review guide postedBucket SortNo longer a comparison-based sorting algorithmInstead a parallel sorting algorithmSort values into individual "buckets"Re-arrange them within the bucket into a sorted orderCombine buckets back into array or listHere we scatter (into buckets) and gather (back into the array) rather than divide and conquerMainly useful when input is uniformly distributed over a rangeVisualizing Bucket SortScatter elements into their respective binsSort elements inside of bins and return to the arrayImage sourceBucket Sort In Under 40 SecondsVideoBucket Sort PseudocodebucketSort(A[], k) //pass in k = number buckets and an array A to sort    List buckets[k] //an array of Lists or array of arrays to be our buckets    for i = 0 to array_size-1        insert array[i] into buckets[correctBucket(array[i])]    for i = 0 to k-1 //for all the buckets        sort(buckets[i])//call sorting algorithm of choice    return concat(buckets[0]...buckets[k-1])    Time Complexity of Bucket SortBest Case: O(n + k) //k = number of bucketsWorst Case: O(n2) //if all elements in one bucket and sort with slow sorting algorithmAverage Case: O(n + k)Final Project Presentations~See You Thursday!~