Bucket sort

From Free net encyclopedia

Image:Bucket sort 1.png Image:Bucket sort 2.png Bucket sort, or bin 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

[edit]

Pseudocode

function bucket-sort(array, n) is
  buckets ← new array of n empty lists
  for i = 1 to n do
    insert array[i] into buckets[msbits(array[i])]
  for i = 0 to n - 1 do
    next-sort(buckets[i])
  return the concatenation of buckets[0], ..., buckets[n-1]

Here array is the array to be sorted and n is the number of buckets. The function msbits(x) should return 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. The function next-sort is a sorting function; using bucket-sort itself as next-sort produces a relative of radix sort; in particular, the case n = 2 corresponds to quicksort (although potentially with poor pivot choices).