## Bucket Sort

Back to Programming

### Description

Bucket sort is a sorting algorithm in which the array elements are distributed into different buckets that are sorted individually. The sorting can be done using some other sorting algorithms or it can be done by calling the bucket sort function recursively. This is a distribution sort. The complexity of this sorting technique depends on the sorting algorithm used to sort the elements of the bucket. Here, insertion sort is used to sort the elements of the bucket.

Bucket sort can be divided into four phases:

1. Initially, the empty buckets are created.

2. The original array is scanned and each element is inserted into the appropriate bucket.

3. The elements of each bucket are sorted individually.

4. The elements of the buckets are gathered and inserted back to the array.

The bucket sort is applied if the elements of the array are uniformly distributed over a range. Here, the range of the elements is taken from 0.0 to 1.0. the buckets are taken according to the range of the elements.

EXAMPLE:

Suppose the array elements are:

Suppose, 10 buckets are created to store the array elements. Here, the index of the bucket for each element is calculated as n*arr[i] where n is the number of elements of the array and arr[i] is the ith element of the array.

Initially, the buckets are initialized with a null value.

The first element of the array is 0.14. Now, it will be multiplied by 5 (here, n = 5). Therefore, we get the index of the bucket as: integer (0.14 × 5) = 0. Therefore, the element will be added to bucket 0.

Now, the next element of the array is 0.25. The same procedure will be followed. The index of the bucket is: integer of 0.25 × 5 = 1.

So, this element will be inserted into bucket 1.

Similarly, the indexes of the next elements are:

Integer of 0.10 × 5 = 0

Integer of 0.19 × 5 = 0

Integer of 0.02 × 5 = 0

Therefore, all the elements will be inserted into bucket 0.

Now, the elements of bucket ‘0’ will be sorted using insertion sort. After sorting the bucket ‘0’ we will get the bucket as:

Therefore, all the elements will be inserted into bucket 0.

For details about insertion sort follow:

bucket 1 contains a single element. Now it will be inserted back to the original array

So, after sorting the array will be:

### Algorithm

``````INPUT: The array elements
OUTPUT: Array after sorting using bucket sort

PROCESS:
Step 1: [Function ‘bucket_sort(array,n)’]
[Creating a bucket]
Create a list b
for i=0 to n-1 repeat
Set b[i]<-Null
[End of ‘for’ loop]
for i=0 to n-1 repeat
Set bi <- integer of  n * j
Create a node with the data arr[i]
Append the node with b[bi]
[End of ‘for’ loop]
for i =0 to n-1 repeat
Sort the list b[i]
[End of ‘for’ loop]
for i=0 to n-1 repeat
put the elements of each list (b[i]) into the original array ‘arr’
[End of ‘for’ loop]
[End of function ‘bucket_sort()’]

Step 2: [Function ‘main()’]
For i= 0 to n-1 repeat
[End of ‘for’ loop]
Call the function ‘bucket_sort(arr,n)’
[End of ‘main’ function]

Step 3: Stop.
``````

### Code

CHARACTERISTICS:

1. The input is taken from a particular range.

2. It is a non-comparative sort.

3. The complexity depends on the number of elements and the number of buckets.

4. The extra auxiliary memory spaces are required for the buckets.

5. It is a distributive sorting technique.

TIME COMPLEXITY:

The complexity of bucket sort depends on the sorting algorithm used to sort the elements of the bucket. Here, insertion sort is used as the sorting algorithm.

Best case:

The best-case occurs when the elements are distributed in the buckets uniformly. Here n is the number of elements of the array then the complexity to make the bucket is O(n) and the complexity to sort the elements of the bucket is O(k)

Therefore,

Average case:

The average case complexity occurs if the elements are randomly distributed. If the elements are not distributed uniformly, then also the bucket sort runs in a linear time.

Therefore,

Worst case:

The worst-case complexity occurs where the elements are in a very close range in the array. Therefore, they are placed in the same bucket. The insertion sort is used here to sort the elements of the array.

Therefore,

Worst case scenario occurs when all the elements are placed in a single bucket.

The worst-case complexity of insertion sort can be calculated as:

SPACE COMPLEXITY:

The space complexity of bucket sort is O(n*k) where n is the number of elements and k is the number of buckets.

1. It is a stable sorting algorithm.

2. If the data are evenly distributed then the sorting is very fast.

3. Primarily it does not depend on the comparison.

4. As the elements are distributed over a number of arrays, then the array elements to be sorted are small.

5. The bucket sort works better if a large degree of parallelism is available.

6. It can be used as an external sorting algorithm also.

1. If the distribution of the buckets is not uniform then the complexity of the sorting will increase.

2. This sorting cannot be applied to all data types.

3. The choice of the bucket is fixed for a particular range of data. If the data is not in that range then the sorting will not work properly.

4. This algorithm is written for the input range from 0.0 to 1.0. if the range is changed, then the method of choice of the bucket will also change.

APPLICATIONS:

1. Bucket sort is used as an external sorting algorithm.

2. It is applied while the data are uniformly distributed.

Related

Contributed by