CP164 Study Guide - Final Guide: Bucket Sort, Radix Sort, Radix
Sorting Continued
The earlier sorting methods discussed are all comparison based sorts, and the best time
complexity we can expect from them is O(n log n). However, there are non-comparison based
sorts that run faster.
Bucket Sort
The Main Idea: sort the elements into buckets. For this sort to work you must know ahead of
time what the range of values you are working with is. Then consider that you have one bucket
for each element in the range. So if your array may contain integers from 1 to 10 you must have
10 buckets labelled 1 to 10. Each bucket contains a running count. As you read elements from
the array, if the element is i, increment the count in bucket i by 1. After you have read the entire
array, you can use the counts to reconstruct the sorted list.
Bucket Sort Analysis
This sort is O(n+m) where m is the size of the range. If m==n as is often the case, this reduces
to O(n) - linear time.
Radix Sort
The Main Idea: like the bucket sort, but works with much larger ranges. It applies to
sorting n numbers in the range 0 to np-1 for some p. It consists of successive bucket-style sorts.
In the base 10 version (there are others), imagine that there are 10 buckets labelled 0 to 9. Into
any bucket i goes all numbers whose 1s digit is i. Then concatenate the contents of the buckets in
order and sort again. This time bucket i gets all numbers whose 10s digit is i. You may keep
making passes with the 100s digit, the 1000s digit, etc.
Example
Sort: 36, 9, 0, 25, 1, 49, 64, 16, 81, 4
The first pass is:
Bucket
Values
0
0
1
1, 81
2
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
The earlier sorting methods discussed are all comparison based sorts, and the best time complexity we can expect from them is o(n log n). However, there are non-comparison based sorts that run faster. The main idea: sort the elements into buckets. For this sort to work you must know ahead of time what the range of values you are working with is. Then consider that you have one bucket for each element in the range. So if your array may contain integers from 1 to 10 you must have. As you read elements from the array, if the element is i, increment the count in bucket i by 1. After you have read the entire array, you can use the counts to reconstruct the sorted list. This sort is o(n+m) where m is the size of the range. If m==n as is often the case, this reduces to o(n) - linear time.
