Welcome to Lesson 19!

Announcements
  • Project Report 5 due today
  • Lab 10 due Thursday
  • Return Quizzes
    • Practice quiz only on Thursday due to time constraints
  • Project Presentations
    • Teams 1, 8, 7, 2 today
  • Final Exam one week from today


Bucket Sort
  • No longer a comparison-based sorting algorithm
  • Instead a parallel sorting algorithm
  • Sort values into individual "buckets"
  • Re-arrange them within the bucket into a sorted order
  • Combine buckets back into array or list
  • Here we scatter (into buckets) and gather (back into the array) rather than divide and conquer
  • Mainly useful when input is uniformly distributed over a range


Visualizing Bucket Sort

Scatter elements into their respective bins

Sort elements inside of bins and return to the array

Bucket Sort In Under 40 Seconds
Bucket Sort Pseudocode

bucketSort(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 Sort
  • Best Case: O(n + k) //k = number of buckets
  • Worst Case: O(n2) //if all elements in one bucket and sort with slow sorting algorithm
  • Average Case: O(n + k)

Final Project Presentations


~See You Thursday!~