DSA by Mitul in C++, Python, and Java : Bucket sort
Published: 2022-11-11 00:26:43

Here we will create buckets and distribute elements of array into buckets. Sort bucket individually and then merge buckets after sorting.

So, this is the array we are going to sort using bucket sort.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/v6jqbkry9yzppaih1nrk.png)
 Lets create some buckets using this law:

`Number of buckets= round(sqrt(number of elements))`

As we have 9 elements, we will create 3 buckets.Tell me why! 

Now we need to decide which number goes to which bucket. Use this formula:
`Appropriate bucket=cell(Value*number of buckets*maxValue`

Here maxValue is 9.
Now, lets start to find the bucket for number 5 as it is the first number.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rn0r2oyev6rs63y8jhvq.png)

Here Appropriate bucket= cell(5*3/9)==2
as the value was 5. Bucket we have 3 and maxValue=9 , we get appropriate bucket for 5 is the number 2 bucket.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ihsrbehlpp3wwwfqmuxt.png)

We have moved it to the bucket 2.
For the number 3, we have:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5v79keqi7isvhhlmej61.png)

For the number 4, we have:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gibds8xoxtf01x7so904.png)

Thus the process follows like this:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8in7ailbts3jubebnx86.png)

It goes on and on. Finally we have:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/w89mqgxv1tucjo1qbwv5.png)


Now let;s sort each bucket using any of our choice(You can use any algorithm to sort a particular bucket).


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0uv4j6x31v1qwx6lfbb5.png)

After 3 buckets are sorted, we have:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/i5jl83ld9xxntcwb4g25.png)



Now we need to add values from bucket to the main array. First we will use bucket 1

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/an2flox4fjsvzwjqnzrc.png)

Then 2nd one:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/at2ct5ziqikefvga7lds.png)

then 3rd one:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nu4tal00w6cmz1v1snux.png)

Finally, we have

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/na1k8shh27dgbd3y3662.png)


**Code for Bucket sort**

```
def bucketSort(customList):
    numberofBuckets = round(math.sqrt(len(customList)))
    maxValue = max(customList)
    arr = []

    for i in range(numberofBuckets):
        arr.append([])
    for j in customList:
        index_b = math.ceil(j*numberofBuckets/maxValue)
        arr[index_b-1].append(j)
    
    for i in range(numberofBuckets):
        arr[i] = insertionSort(arr[i])
    
    k = 0
    for i in range(numberofBuckets):
        for j in range(len(arr[i])):
            customList[k] = arr[i][j]
            k += 1
    return customList
```




**Complexity Analysis**

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/41fx33xir9sjpdv1vc3l.png)


**When to use Bucket Sort?**
1. When input uniformly distributed over range. That means there is not a huge gap between values in the list.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qkavaj4kqh6ny7dqxfum.png)

**When to avoid Bucket sort?**
When space is a concern.