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:
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:
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()’]
Read n [number of elements]
For i= 0 to n-1 repeat
Read arr[i]
[End of ‘for’ loop]
Call the function ‘bucket_sort(arr,n)’
[End of ‘main’ function]
Step 3: Stop.
CHARACTERISTICS:
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, the best case complexity of the bucket sort is O(n+k).
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, the complexity of bucket sort in the average case is O(n).
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, the worst-case complexity of this algorithm is O(n2) which is the worst-case complexity of the insertion sort.
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:
f(n) = 1+2+3+4+………+(n-1)
= n (n-1) / 2
= n2/2 - n/2
= O(n2)
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.
ADVANTAGES:
DISADVANTAGES:
APPLICATIONS:
Related
Contributed by