Bucket Sort Implementation in Python

Bucket sort is a sorting algorithm that divides an array into a number of equally sized subarrays or buckets, each of which is sorted individually. The idea is to spread the elements of the input array into a number of buckets, and then sort each bucket individually using a different sorting algorithm or by recursively applying the bucket sorting algorithm. After all the buckets are sorted, the algorithm combines the buckets into the final sorted array.

How does Bucket Sort Algorithm work?

The bucket sort algorithm can be summarized in the following steps:

1. Divide the input array into n buckets.
2. For each bucket, insert its elements into a linked list and sort them using insertion sort or any other sorting algorithm.
3. Concatenate the sorted linked lists in order, and that is the sorted array.

The idea is to distribute the elements of the input array into buckets based on their value, such that elements with similar values are placed into the same bucket. Each bucket is then sorted individually using insertion sort or any other sorting algorithm, and the sorted buckets are concatenated into the final sorted array.

Bucket Sort Algorithm Implementation in Python

Here’s an implementation of the bucket sort algorithm in Python:

def bucket_sort(arr):
    # Create an empty list for each bucket
    buckets = [[] for _ in range(len(arr))]
    
    # Calculate the maximum value in the input array
    max_val = max(arr)
    
    # Divide the elements into buckets based on their value
    for num in arr:
        index = int(num / (max_val + 1) * len(arr))
        buckets[index].append(num)
    
    # Sort each bucket and concatenate them into the final array
    sorted_arr = []
    for bucket in buckets:
        sorted_arr += sorted(bucket)
    
    return sorted_arr

The above code first creates an empty list for each bucket, then calculates the maximum value in the input array, and finally divides the elements into buckets based on their value. The buckets are then sorted using the built-in sorted function in Python, and concatenated into the final sorted array.

Time and Space Complexity

The time complexity of the bucket sort algorithm depends on the sorting algorithm used to sort the individual buckets. In the worst case, if all the elements are placed into the same bucket, the time complexity becomes O(n^2). However, if the buckets are evenly distributed, the time complexity becomes O(nlogn).

The space complexity of the bucket sort algorithm is O(n + k), where n is the number of elements in the input array and k is the number of buckets. If the number of buckets is much smaller than the number of elements in the input array, the space complexity can be considered as O(n).

Example Run

Let’s run the above implementation of the bucket sort algorithm on an input array of integers:

arr = [29, 25, 3, 49, 9, 37, 21, 43]

sorted_arr = bucket_sort(arr)

print("Sorted Array:", sorted_arr)

The output of the above code should be:

Sorted Array: [3, 9, 21, 25, 29, 37, 43, 49]

The above code sorts the input array using the bucket sort algorithm and returns the sorted array. As we can see from the output, the input array is sorted in ascending order using the bucket sort algorithm.

Conclusion

Bucket sort is a simple and efficient sorting algorithm that works by dividing the input array into a number of equally sized buckets, and then sorting each bucket individually using insertion sort or any other sorting algorithm. The sorted buckets are then concatenated into the final sorted array. The time complexity of the bucket sort algorithm depends on the sorting algorithm used to sort the individual buckets, and the space complexity is O(n + k), where n is the number of elements in the input array and k is the number of buckets. Bucket sort is a good choice for sorting data that is uniformly distributed across a range of values.