Bucket (Bin) Sort
Objectives
We would like to :- Examine bucket short
Notes
- Assumes a key that "classified" into one of n buckets or bins
- For example:
- For integers between min and max
- binEdgeDelta = (max-min)/10
- The bins are (min, min+binEdgeDelta) , ... (max-binEdgeDelta, max)
- There is an assumption that the data is uniformaly distributed, ie it will fall equally between the bins.
-
Bucket-Sort(A,k) A is the array k is the number of buckets- let M = max value in the array
- let B[0, ... k-1] be a new empty array
- for i ← 0 to A.size
- insert A[i] into B[⌊ k * A[i] / M ⌋]
- for i ← 0 to B.size
- Sort B[i]
- Make A empty
- for i ← 0 to B.size
- Append B[i] into A
- Worst case is O(n2) if all data falls in the same bin.
- Expected is (n+k), but that is hard
- Space is O(n+k)