Encyclopedia > Bucket sort

  Article Content

Bucket sort

Bucket 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 when input is drawn from a uniform distribution.

It works as follows:

  1. Set up an array of initially empty "buckets" the size of the range.
  2. Go over the original array, putting each object in its bucket.
  3. Sort each non-empty bucket.
  4. 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 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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Michael Barrymore

... Barrymore, born 4 May 1952, is a British comedian famous for his variety shows. This article is a stub. You can help Wikipedia by fixing it. Early ...

 
 
 
This page was created in 27.5 ms