|
|
Bucket SortBucket sort is a sort algorithm that works by partitioning an array into a finite number of buckets and then sorting each bucket. It is a generalization of pigeonhole sort. Bucket sort runs in linear time (Θ(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(n) returns the most significant bits of n. ' This could be k*n for sorting numbers, or ' the first character of n 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 Ai into list BMSBITS(A[i)] for i = 0 to n - 1: NEXT-SORT(Bi) concatenate the lists B0...Bn-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.
|
 |