# Bucket Sort

Bucket sort is also known as bin sort. It is a sorting algorithm that divides an array’s items into a number of buckets. The buckets are then sorted one at a time, either using a separate sorting method or by recursively applying the bucket sorting algorithm.

Assumption : Input data is generated by some random process and uniformly distributed in the range of [0, 1).

Bucket sort sorts the data by partitioning them into n buckets. Each number is stored in an appropriate bucket. Numbers in a bucket are sorted using some linear time algorithm. Inputs are uniformly distributed so it is less likely to fall many numbers in a single bucket.

Bucket sort operates in two stages:

• Scatter: Distribute all the elements in their respective buckets. Sort all the buckets
• Gather: Visit all buckets in order and put all the data in original array

## Example of Bucket Sort

Example: Trace bucket sort with following data {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68}.

Solution:

Ten bins/buckets are created and elements of array A is inserted in the appropriate bin number integer of [n*A[i]]. Following diagram shows the Input data pattern and sorted bins. Insert element in a linked list using insertion sort.

Read values from each bucket in same order, so sorted data would be B {0.12, 0.17, 0.21, 0.23, 0.28, 0.39, 0.68, 0.72, 0.78, 0.94}.

Example: Sort the array A {0.23, 0.65, 0.11, 0.37, 0.45, 0.63, 0.18, 0.87, 0.92, 0.25} using bucket sort.

Solution:

Ten buckets are created and elements of array A is inserted in the appropriate bucket number integer of [n*A[i]]. Following diagram shows the Input data pattern and sorted buckets. Insert element in a linked list using insertion sort.

Read values from each bucket in the same order, so sorted data would be B{0.11, 0.18, 0.23, 0.25, 0.37, 0.45, 0.63, 0.65, 0.87, 0.92}

## Algorithm of Bucket Sort

Algorithm BUCKET_SORT(A)
// A is an array of size n

Create n buckets represented by B
for i ← 1 to n do
Insert A[i] into bucket B[n*A[i]]
end

for i ← 1 to n do
sort each bucket i using insertion sort
end
Concate all buckets into sorted order

## Complexity Analysis

• This technique is most useful when the input is evenly spread throughout a range.
• Adjacent keys (elements with almost similar values) are placed in one bucket, which makes distribution uneven. Some buckets will contain more elements, while others will have fewer elements.
• The worst case occurs when all elements create a tight cluster and fall into the same bucket. In this case, the running time of the algorithm would be O(n2)
• If the size of each bucket is one, the performance of bucket sort reduces to counting sort.
• In general, the time complexity of bucket sort is O(n + m), where n is the number of elements in the array and m is the range of input values.

• Because of the uniform distribution, it is asymptotically fast.
• It reduces the number of comparisons.
• When compared to bubble sort, it is faster.

## Limitations of Bucket Sort

• It is not suitable for sorting arbitrary strings.
• It is only good for sorting data uniformly distributed over the range [0, 1].
• It is not an in-place sorting because the buckets require additional space to be sorted.
• It is ineffective if we have a huge array since it increases the cost.
• Prior knowledge of the greatest element is required.

Following are the few popular sorting algorithms used in computer science: