Python Program for Bucket Sort

In this article, we will study the bucket sort and its algorithm with python code along with its output.

Bucket Sort is a comparison-type algorithm which assigns elements of a list we want to sort in Buckets, or Bins. The contents of these buckets are then sorted, typically with another algorithm. After sorting, the contents of the buckets are appended, forming a sorted collection.

Example :

    
# python program for bucket sort
def InsertionSort(bucket):
    for i in range (1, len (bucket)):
        var = bucket[i]
        j = i - 1
        while (j >= 0 and var < bucket[j]):
            bucket[j + 1] = bucket[j]
            j = j - 1
        bucket[j + 1] = var

def BucketSort(arr):
    max_val = max(arr)
    size = max_val/len(arr)

    buckets_list= []
    for x in range(len(arr)):
        buckets_list.append([]) 

    for i in range(len(arr)):
        j = int (arr[i] / size)
        if j != len (arr):
            buckets_list[j].append(arr[i])
        else:
            buckets_list[len(arr) - 1].append(arr[i])

    for z in range(len(arr)):
        InsertionSort(buckets_list[z])
            
    sorted = []
    for x in range(len (arr)):
        sorted = sorted + buckets_list[x]
    return sorted

arr = [45,22,65,78,9,23,89,52]

print("Before Sorted :: ",arr)
print("After Sorted :: ",BucketSort(arr))
       

Output :

    
Before Sorted ::  [45, 22, 65, 78, 9, 23, 89, 52]
After Sorted ::  [9, 22, 23, 45, 52, 65, 78, 89]