Bucket sort
Bucket sort is a sort algorithm that works by partitioning an array into a finite number of bucketss and then sorting each bucket.
It is a generalization of pigeonhole sort.
Bucket sort runs in linear time (&Theta(n)) when input is drawn from a uniform distribution. Not being a comparison sort, it is not subject to the Ω(n log n) lower bound. It works as follows: Set up an array of initially empty "buckets" the size of the range. Go over the original array, putting each object in its bucket. Sort each non-empty bucket. Put elements from non-empty buckets back into the original array.
Pseudocode ' A is the array
' n is the number of buckets
' MSBITS(x) returns the most significant bits of x.
' This could be floor(x/2^k) (where k is a
' nonnegative integer) for sorting numbers, or
' the first character of x for sorting strings.
' NEXT-SORT is a sort algorithm
BUCKET-SORT(A, n, MSBITS, NEXT-SORT):
make array B of n lists
for i = 1 to n:
insert A[i] into list B[MSBITS(A[i])]
for i = 0 to n - 1:
NEXT-SORT(B[i])
concatenate the lists B[0]...B[n-1] in order
Relationships to other sorting algorithms
Using BUCKET-SORT itself as the NEXT-SORT produces a relative of the radix sort.
Using BUCKET-SORT with n == 2 and itself as the NEXT-SORT produces quicksort.
|
|
