Welcome to Lesson 18!
Learning Objectives By the end of this class, you should know...
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(n^{2}) //if all elements in one bucket and sort with slow sorting algorithm
- Average Case: O(n + k)
Project Presentations |