• Bucket sort

Image:



Definition:
It is also called bin sort.

It is a sorting algorithm that works by partitioning it into a number of buckets. Each bucket is then sorted individually using the different sorting algorithm, or by recursively applying the bucket sorting algorithm.

Bucket sort works as follows:

1. Set up an array of initially empty "buckets."
2. Scatter: Go over the original array, putting each object in its bucket.
3. Sort each non-empty bucket.
4. Gather: Visit the buckets in order and put all elements back into the original array.

Run-time Complexity Analysis:
♥ efficient and effective in sorting the list.

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

Application:
♥ Given an array, put the array of numbers in a bucket where they must be placed then sort the list.

Reference:

• commons.wikimedia.org/wiki/File:Bucket_sort_2.png
• http://en.wikipedia.org/wiki/Bucket_sort