Bucket Sort Algorithm: A Simple and Efficient Sorting Technique in Python

Bucket Sort is a linear time sorting algorithm that works by partitioning an array into a number of buckets, each of which is then sorted individually using another sorting algorithm, typically insertion sort. In this blog, we will explore the implementation of Bucket Sort in Python.

Bucket Sort Algorithm

The Bucket Sort algorithm works by dividing the input array into a number of buckets, where each bucket can hold a range of values. We then insert each element in the input array into the corresponding bucket. Finally, we sort each bucket individually using another sorting algorithm, typically insertion sort, and then concatenate the sorted buckets to obtain the sorted output.

Here's the algorithm for Bucket Sort:

Create a list of empty buckets.

1. For each element in the input array, compute the bucket number and insert the element into the corresponding bucket.
2. Sort each bucket individually using another sorting algorithm, typically insertion sort.
3. Concatenate the sorted buckets to obtain the sorted output.
4. Bucket Sort Implementation in Python
5. Let's implement the Bucket Sort algorithm in Python:

def bucket_sort(arr, bucket_size=5):
    max_val = max(arr)
    bucket_count = (max_val // bucket_size) + 1
    buckets = [[] for _ in range(bucket_count)]
    
    # Insert each element in the input array into the corresponding bucket
    for num in arr:
        bucket_index = num // bucket_size
        buckets[bucket_index].append(num)
    
    # Sort each bucket individually using insertion sort
    for i in range(bucket_count):
        buckets[i].sort()
    
    # Concatenate the sorted buckets to obtain the sorted output
    sorted_arr = []
    for bucket in buckets:
        sorted_arr += bucket
    
    return sorted_arr

In the bucket_sort function, we first compute the maximum value in the input array and calculate the number of buckets required based on the given bucket size. We then create a list of empty buckets.

We insert each element in the input array into the corresponding bucket based on its value. We then sort each bucket individually using another sorting algorithm, typically insertion sort. Finally, we concatenate the sorted buckets to obtain the sorted output.

Conclusion

Bucket Sort is a linear time sorting algorithm that works by partitioning an array into a number of buckets, each of which is then sorted individually using another sorting algorithm, typically insertion sort. The implementation of Bucket Sort in Python is relatively simple and requires only a few lines of code. Bucket Sort can be useful for sorting data that is uniformly distributed over a range of values and has a small variation. However, it may not be as efficient as other sorting algorithms for sorting large datasets with a large variation in values.

Here is detail on each sorting algorithm in python