Bucket Sort in Python

Bucket sort is a sorting technique that involves dividing elements into various groups, or buckets. These buckets are formed by uniformly distributing the elements. Once the elements are divided into buckets, they can be sorted using any other sorting algorithm. Finally, the sorted elements are gathered together in an ordered fashion.

Bucket Sort Algorithm:

• Create an array of empty buckets.
• Iterate through the input array and distribute each element into the corresponding bucket based on some criteria.
• Sort each bucket individually (using another sorting algorithm or recursively applying bucket sort).
• Concatenate all the sorted buckets to get the final sorted array.

How does Bucket Sort work?

To apply bucket sort on the input array [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68], we follow these steps:

• Step 1: Create an array of size 10, where each slot represents a bucket.
• Step 2: Insert elements into the buckets from the input array based on their range.
• Step 3: Sort the elements within each bucket. In this example, we use quicksort (or any stable sorting algorithm) to sort the elements within each bucket.
• Step 4: Gather the elements from each bucket and put them back into the original array.
• Step 5: The original array now contains the sorted elements.

The final sorted array using bucket sort for the given input is [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94].

Implementation of Bucket Sort in Python:

Below is the implementation of bucket sort in python:

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

def bucket_sort(arr):
    n = len(arr)
    buckets = [[] for _ in range(n)]

    # Put array elements in different buckets
    for num in arr:
        bi = int(n * num)
        buckets[bi].append(num)

    # Sort individual buckets using insertion sort
    for bucket in buckets:
        insertion_sort(bucket)

    # Concatenate all buckets into arr[]
    index = 0
    for bucket in buckets:
        for num in bucket:
            arr[index] = num
            index += 1

arr = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
bucket_sort(arr)
print("Sorted array is:")
print(" ".join(map(str, arr)))

Sorted array is:
0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94

Complexity Analysis of Bucket Sort Algorithm:

Time Complexity: O(n²),

• If we assume that insertion in a bucket takes O(1) time then steps 1 and 2 of the above algorithm clearly take O(n) time.
• The O(1) is easily possible if we use a linked list to represent a bucket.
• Step 4 also takes O(n) time as there will be n items in all buckets. 
• The main step to analyze is step 3. This step also takes O(n) time on average if all numbers are uniformly distributed.

Auxiliary Space: O(n+k)