Python Program to Implement Bucket Sort

This Python program implements Bucket Sort, a sorting algorithm that divides the input data into buckets and then sorts each bucket individually, typically using another sorting algorithm like insertion sort.

Bucket Sort is a sorting algorithm that works by distributing the elements of an array into a number of buckets, sorting each bucket individually, and then concatenating the sorted buckets to obtain the sorted array.

Problem Statement

Given an array of floating-point numbers, implement Bucket Sort to sort the array in ascending order.

Python Program to Implement Bucket Sort

def insertion_sort(bucket):
    for i in range(1, len(bucket)):
        key = bucket[i]
        j = i - 1
        while j >= 0 and key < bucket[j]:
            bucket[j + 1] = bucket[j]
            j -= 1
        bucket[j + 1] = key

def bucket_sort(arr):
    # Determine the number of buckets to use
    num_buckets = len(arr)
    
    # Create empty buckets
    buckets = [[] for _ in range(num_buckets)]
    
    # Distribute elements into buckets
    for num in arr:
        index = int(num * num_buckets)
        buckets[index].append(num)
    
    # Sort each bucket using insertion sort
    for bucket in buckets:
        insertion_sort(bucket)
    
    # Concatenate sorted buckets
    sorted_array = []
    for bucket in buckets:
        sorted_array.extend(bucket)
    
    return sorted_array

# Input
arr = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]

# Output
sorted_arr = bucket_sort(arr)
print("Original Array:", arr)
print("Sorted Array:", sorted_arr)

How it Works

1. Determine the number of buckets to be used. In this example, we’re using the same number of buckets as the length of the input array.
2. Create empty buckets.
3. Distribute elements from the input array into the buckets based on their value. Each element is multiplied by the number of buckets, and the resulting integer part is used as the index for the bucket.
4. Sort each individual bucket using an auxiliary sorting algorithm (in this case, we’re using Insertion Sort).
5. Concatenate the sorted buckets to obtain the final sorted array.

Input/Output