Implementation of Bucket sort in Python

Hi, in this tutorial we are going to learn how to implement bucket sort using Python. Bucket sort is mainly useful when data is uniformly distributed over a range. This sorting technique is also known as bin sort.

Bucket sort in Python – Implementation

In bucket sort, we create n no. of buckets to sort n no. of data. After creating buckets we distribute the data into these buckets and then sort these buckets individually. And after sorting each bucket we gather the data and add it to the original list and return that list. So, let’s see the code now:

l=[0.91,0.3,0.53,0.22,0.23,0.76]
m=[]
for i in range(len(l)):
    m.append([])
    
k=len(l)
for i in range(0,k):
    b=int(l[i]*k)
    m[b].append(l[i])

for j in range(0,k):
    m[j].sort()

index=0
for i in range(0,k):
    for j in range(0,len(m[i])):
        l[index]=m[i][j]
        index+=1
print("Sorted data is:")        
print(l)

Here, we first declare a list l, containing data that is distributed uniformly over the range 0.0 to 1. Then, we declare list m, which contain buckets. Then we create buckets inside list m.

To distribute data elements into the buckets we multiply every data element by the total no. of data elements. And then store the product into variable b. Then append that element inside list m into bth buckets.

After distributing the data into buckets, we sort each bucket individually. For sorting each bucket we can use any sorting algorithm like insertion sort, quick sort, or bucket sort indeed. Here, we use Python built-in method sort() which is used to sort the data in ascending order.

Finally, we concatenate all the sorted into the original list l. Then, we print the list l.

Output:

Sorted data is:
[0.22, 0.23, 0.3, 0.53, 0.76, 0.91]

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *