Bucket Sort using Python

 

Bucket sort is an efficient sorting algorithm that works by distributing the elements of the input list into a number of "buckets" and then sorting the elements in each bucket. The final sorted list is obtained by concatenating the sorted elements in each bucket.

Here is an implementation of bucket sort in Python:

def bucket_sort(arr, n):
    # Create n empty buckets
    buckets = [[] for _ in range(n)]
    
    # Distribute the elements of the input list into the buckets
    for x in arr:
        buckets[int(n*x)].append(x)
    
    # Sort the elements in each bucket
    for bucket in buckets:
        bucket.sort()
    
    # Concatenate the sorted elements in the buckets
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(bucket)
    
    return sorted_arr

# Test the function
arr = [0.2, 0.5, 0.1, 0.3, 0.4]
print(bucket_sort(arr, len(arr)))  # Output: [0.1, 0.2, 0.3, 0.4, 0.5]

In this implementation, the input list is assumed to contain elements in the range [0, 1]. The elements are distributed into n buckets, where n is the length of the input list. The bucket index for each element is determined by multiplying the element by n, which maps the element to an integer in the range [0, n-1]. For example, if n=5, the element 0.2 is mapped to the bucket at index 1, and the element 0.5 is mapped to the bucket at index 2.

The elements in each bucket are then sorted using a stable sorting algorithm, such as insertion sort. Finally, the sorted elements in each bucket are concatenated to obtain the final sorted list.

Bucket sort has a time complexity of O(n) if the elements of the input list are uniformly distributed and the sorting algorithm used to sort the elements in each bucket is O(1). However, if the elements are not uniformly distributed, the time complexity of bucket sort may degrade to O(n^2).

Using Recursion

It is possible to implement bucket sort using recursion, by dividing the input list into smaller sublists and sorting each sublist using bucket sort. Here is an example of a recursive implementation of bucket sort in Python:

def bucket_sort_recursive(arr, n):
    # Base case: the list has only one element
    if n == 1:
        return arr
    
    # Divide the input list into two sublists
    mid = n // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # Sort the sublists recursively
    left = bucket_sort_recursive(left, len(left))
    right = bucket_sort_recursive(right, len(right))
    
    # Merge the sorted sublists
    sorted_arr = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1
    sorted_arr.extend(left[i:])
    sorted_arr.extend(right[j:])
    
    return sorted_arr

# Test the function
arr = [0.2, 0.5, 0.1, 0.3, 0.4]
print(bucket_sort_recursive(arr, len(arr)))  # Output: [0.1, 0.2, 0.3, 0.4, 0.5]

This recursive implementation of bucket sort first divides the input list into two sublists, and then sorts each sublist recursively using bucket sort. The sublists are then merged to obtain the final sorted list.

The time complexity of this recursive implementation of bucket sort is O(nlogn) if the elements of the input list are uniformly distributed, because the list is divided into smaller sublists and sorted recursively. However, if the elements are not uniformly distributed, the time complexity may degrade to O(n^2logn).