Welcome to Lesson 18!

Learning Objectives
By the end of this class, you should know...
  • Bucket sort


Announcements

  • Last Quiz Wednesday
    • Will ask you to trace merge sort in action
    • Will ask you to write the pseudocode for mergesort (NOT the helper function merge)
    • Heap Questions
    • AVL Tree Questions
  • Project Report 5 due Wednesday, December 2
  • Assignment 5 due Thursday
  • Project Presentations next week
    • Teams 1-4 today
    • Teams 5-8 on Wednesday

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
    List buckets[k]
    for i = 0 to array_size-1
        insert array[i] into buckets[correctBucket(array[i])]
    for i = 0 to k-1
        sort(buckets[i])
    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)


Project Presentations

  • Teams 1- 4