DSA by Mitul in C++, Python, and Java : Bucket sort

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.

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.

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.

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

For the number 4, we have:

Thus the process follows like this:

It goes on and on. Finally we have:

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

After 3 buckets are sorted, we have:

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

Then 2nd one:

then 3rd one:

Finally, we have

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

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.

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