Python Program to Implement Bucket Sort

Sorting is a vital skill in programming, and understanding different sorting algorithms helps Python beginners handle data efficiently. One of the interesting and intuitive algorithms is Bucket Sort. Unlike comparison-based algorithms such as Quick Sort or Merge Sort, Bucket Sort distributes elements into separate “buckets” and then sorts each bucket individually. This approach makes it particularly useful for data that is uniformly distributed across a range.

Bucket Sort is often used in applications like grading systems, sorting floating-point numbers, or large datasets where values are spread across a known range. Learning Bucket Sort introduces beginners to the concepts of grouping, distribution, and sublist sorting, all of which are important for more advanced algorithmic thinking. While it may seem slightly different from other sorting algorithms, practicing it step by step makes it easy to understand and apply in Python.

Table of Contents

Toggle

Program 1: Basic Bucket Sort
Program 2: Bucket Sort Using Loops
Program 3: Recursive Bucket Sort
Program 4: Bucket Sort with Dynamic Bucket Count
Program 5: Bucket Sort for Integers
Program 6: Bucket Sort for Integers in a Range
Program 7: Bucket Sort Using Python’s List Comprehension
Frequently Asked Questions (FAQ)
Conclusion

Program 1: Basic Bucket Sort

This program demonstrates the standard approach to Bucket Sort. It divides numbers into buckets, sorts each bucket using Python’s built-in sort() method, and merges the results to produce a sorted list.

def bucket_sort(arr):

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

    for num in arr:
        index = int(num * n)
        buckets[index].append(num)

    for bucket in buckets:
        bucket.sort()

    sorted_arr = []

    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr


numbers = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]

print("Original List:", numbers)

sorted_numbers = bucket_sort(numbers)

print("Sorted List:", sorted_numbers)

def bucket_sort(arr):

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

    for num in arr:
        index = int(num * n)
        buckets[index].append(num)

    for bucket in buckets:
        bucket.sort()

    sorted_arr = []

    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr


numbers = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]

print("Original List:", numbers)

sorted_numbers = bucket_sort(numbers)

print("Sorted List:", sorted_numbers)

In this program, numbers are distributed into buckets based on their value. Sorting individual buckets is easy because each bucket contains a smaller subset of the data. This makes the algorithm both intuitive and efficient for uniformly distributed values.

Program 2: Bucket Sort Using Loops

This version manually sorts each bucket using loops, giving beginners a clearer picture of the algorithm’s internal mechanics.

def bucket_sort_loops(arr):

    n = len(arr)

    buckets = [[] for _ in range(n)]

    for num in arr:
        index = int(num * n)
        buckets[index].append(num)

    for bucket in buckets:

        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

    sorted_arr = []

    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr



numbers = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]

print("Original List:", numbers)

sorted_numbers = bucket_sort_loops(numbers)

print("Sorted List:", sorted_numbers)

def bucket_sort_loops(arr):

    n = len(arr)

    buckets = [[] for _ in range(n)]

    for num in arr:
        index = int(num * n)
        buckets[index].append(num)

    for bucket in buckets:

        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

    sorted_arr = []

    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr



numbers = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]

print("Original List:", numbers)

sorted_numbers = bucket_sort_loops(numbers)

print("Sorted List:", sorted_numbers)

Using loops instead of the built-in sort allows beginners to see exactly how comparisons and swaps work inside each bucket. It reinforces the idea that Bucket Sort is essentially dividing and conquering.

Program 3: Recursive Bucket Sort

This program sorts each bucket recursively, which is an elegant way to handle larger buckets that still need sorting.

def recursive_bucket_sort(arr):

    n = len(arr)

    if n <= 1:
        return arr[:]

    # Handle equal elements (avoid infinite recursion)
    if min(arr) == max(arr):
        return arr[:]

    # Normalize values to range [0, 1)
    min_val, max_val = min(arr), max(arr)
    span = max_val - min_val
    buckets = [[] for _ in range(n)]

    # Place elements into buckets
    for num in arr:
        index = int((num - min_val) / span * (n - 1))
        buckets[index].append(num)

    # Recursively sort buckets and merge results
    sorted_arr = []

    for bucket in buckets:

        if len(bucket) == 0:
            continue
        elif len(bucket) == 1:
            sorted_arr.extend(bucket)
        else:

            # Avoid infinite recursion if all elements fall in one bucket
            if len(bucket) == len(arr):
                sorted_arr.extend(sorted(bucket))
            else:
                sorted_arr.extend(recursive_bucket_sort(bucket))

    return sorted_arr


# Example
numbers = [0.25, 0.36, 0.58, 0.41, 0.29, 0.77]

print("Original List:", numbers)

sorted_numbers = recursive_bucket_sort(numbers)

print("Sorted List:", sorted_numbers)

def recursive_bucket_sort(arr):

    n = len(arr)

    if n <= 1:
        return arr[:]

    # Handle equal elements (avoid infinite recursion)
    if min(arr) == max(arr):
        return arr[:]

    # Normalize values to range [0, 1)
    min_val, max_val = min(arr), max(arr)
    span = max_val - min_val
    buckets = [[] for _ in range(n)]

    # Place elements into buckets
    for num in arr:
        index = int((num - min_val) / span * (n - 1))
        buckets[index].append(num)

    # Recursively sort buckets and merge results
    sorted_arr = []

    for bucket in buckets:

        if len(bucket) == 0:
            continue
        elif len(bucket) == 1:
            sorted_arr.extend(bucket)
        else:

            # Avoid infinite recursion if all elements fall in one bucket
            if len(bucket) == len(arr):
                sorted_arr.extend(sorted(bucket))
            else:
                sorted_arr.extend(recursive_bucket_sort(bucket))

    return sorted_arr


# Example
numbers = [0.25, 0.36, 0.58, 0.41, 0.29, 0.77]

print("Original List:", numbers)

sorted_numbers = recursive_bucket_sort(numbers)

print("Sorted List:", sorted_numbers)

Recursion here demonstrates how the same logic can be applied repeatedly to smaller subsets of data. Beginners can see how breaking a problem down into similar subproblems simplifies complex tasks.

Program 4: Bucket Sort with Dynamic Bucket Count

In this program, the number of buckets is chosen dynamically based on the input size, making the algorithm more adaptable.

def bucket_sort_dynamic(arr):

    n = len(arr)
    bucket_count = max(1, n // 2)
    buckets = [[] for _ in range(bucket_count)]

    max_val = max(arr)

    for num in arr:
        index = int((num / max_val) * (bucket_count - 1))
        buckets[index].append(num)

    for bucket in buckets:
        bucket.sort()

    sorted_arr = []

    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr


numbers = [0.9, 0.7, 0.3, 0.5, 0.8, 0.1]

print("Original List:", numbers)

sorted_numbers = bucket_sort_dynamic(numbers)

print("Sorted List:", sorted_numbers)

def bucket_sort_dynamic(arr):

    n = len(arr)
    bucket_count = max(1, n // 2)
    buckets = [[] for _ in range(bucket_count)]

    max_val = max(arr)

    for num in arr:
        index = int((num / max_val) * (bucket_count - 1))
        buckets[index].append(num)

    for bucket in buckets:
        bucket.sort()

    sorted_arr = []

    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr


numbers = [0.9, 0.7, 0.3, 0.5, 0.8, 0.1]

print("Original List:", numbers)

sorted_numbers = bucket_sort_dynamic(numbers)

print("Sorted List:", sorted_numbers)

By adjusting the number of buckets dynamically, the algorithm becomes flexible for different datasets. Beginners can understand that tuning algorithm parameters can improve performance.

Program 5: Bucket Sort for Integers

Bucket Sort is often used for decimals, but it can also handle integers by normalizing them into buckets.

def bucket_sort_integers(arr):

    n = len(arr)
    max_val = max(arr)
    buckets = [[] for _ in range(n)]

    for num in arr:
        index = int((num / (max_val + 1)) * n)
        buckets[index].append(num)

    for bucket in buckets:
        bucket.sort()

    sorted_arr = []

    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr


numbers = [42, 32, 33, 52, 37, 47, 51]

print("Original List:", numbers)

sorted_numbers = bucket_sort_integers(numbers)

print("Sorted List:", sorted_numbers)

def bucket_sort_integers(arr):

    n = len(arr)
    max_val = max(arr)
    buckets = [[] for _ in range(n)]

    for num in arr:
        index = int((num / (max_val + 1)) * n)
        buckets[index].append(num)

    for bucket in buckets:
        bucket.sort()

    sorted_arr = []

    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr


numbers = [42, 32, 33, 52, 37, 47, 51]

print("Original List:", numbers)

sorted_numbers = bucket_sort_integers(numbers)

print("Sorted List:", sorted_numbers)

This demonstrates that Bucket Sort is versatile and can work for both integers and floating-point numbers. Normalization helps map values into the appropriate buckets efficiently.

Program 6: Bucket Sort for Integers in a Range

Bucket Sort can also be applied specifically to integer datasets. This version shows how to create buckets for integer ranges and sort them efficiently.

def bucket_sort_integers(arr):

    if len(arr) == 0:
        return arr

    max_value = max(arr)
    min_value = min(arr)
    bucket_count = max_value - min_value + 1
    buckets = [[] for _ in range(bucket_count)]

    for num in arr:
        buckets[num - min_value].append(num)

    sorted_arr = []

    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr


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

sorted_numbers = bucket_sort_integers(numbers)

print("Sorted integer list:", sorted_numbers)

def bucket_sort_integers(arr):

    if len(arr) == 0:
        return arr

    max_value = max(arr)
    min_value = min(arr)
    bucket_count = max_value - min_value + 1
    buckets = [[] for _ in range(bucket_count)]

    for num in arr:
        buckets[num - min_value].append(num)

    sorted_arr = []

    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr


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

sorted_numbers = bucket_sort_integers(numbers)

print("Sorted integer list:", sorted_numbers)

Here, each bucket corresponds to a possible integer value in the range of the dataset. By placing integers directly into their corresponding buckets, the algorithm becomes highly efficient. Beginners can appreciate how using the properties of integer ranges allows Bucket Sort to simplify sorting without complex comparisons.

Program 7: Bucket Sort Using Python’s List Comprehension

For a more Pythonic approach, Bucket Sort can be implemented using list comprehension and the built-in sorted() function to organize each bucket. This version is easy to read and beginner-friendly.

def bucket_sort_comprehension(arr):

    if not arr:
        return arr

    min_value, max_value = min(arr), max(arr)
    
    if min_value == max_value:
        return arr  # all numbers are the same

    bucket_count = len(arr)
    buckets = [[] for _ in range(bucket_count)]

    # distribute numbers into buckets
    for num in arr:
        index = int((num - min_value) / (max_value - min_value) * (bucket_count - 1))
        buckets[index].append(num)

    # sort each bucket and flatten the result
    sorted_arr = [num for bucket in buckets for num in sorted(bucket)]
    return sorted_arr


numbers = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]

sorted_numbers = bucket_sort_comprehension(numbers)

print("Sorted list using list comprehension:", sorted_numbers)

def bucket_sort_comprehension(arr):

    if not arr:
        return arr

    min_value, max_value = min(arr), max(arr)
    
    if min_value == max_value:
        return arr  # all numbers are the same

    bucket_count = len(arr)
    buckets = [[] for _ in range(bucket_count)]

    # distribute numbers into buckets
    for num in arr:
        index = int((num - min_value) / (max_value - min_value) * (bucket_count - 1))
        buckets[index].append(num)

    # sort each bucket and flatten the result
    sorted_arr = [num for bucket in buckets for num in sorted(bucket)]
    return sorted_arr


numbers = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]

sorted_numbers = bucket_sort_comprehension(numbers)

print("Sorted list using list comprehension:", sorted_numbers)

In this program, each element is placed into a bucket using a formula based on the minimum and maximum values, and each bucket is then sorted using Python’s built-in sorted() function. This method teaches beginners how Python’s features can simplify algorithm implementation while maintaining the logic behind Bucket Sort.

Frequently Asked Questions (FAQ)

Bucket Sort can raise questions for beginners. Here are some answers to clarify common doubts.

Q1: What is the time complexity of Bucket Sort?
The average-case complexity is O(n + k), where n is the number of elements and k is the number of buckets.

Q2: When should I use Bucket Sort?
It works best for uniformly distributed numbers and datasets where the maximum and minimum values are known.

Q3: Is Bucket Sort stable?
Yes, if the sorting within each bucket is stable, the overall algorithm is stable.

Q4: Can Bucket Sort handle both integers and decimals?
Yes, by normalizing the values into buckets, both types can be sorted efficiently.

Q5: How is Bucket Sort different from Counting Sort?
Bucket Sort divides numbers into ranges (buckets) and sorts each bucket, while Counting Sort counts occurrences of each value directly.

Conclusion

Bucket Sort is a practical and efficient sorting algorithm, especially for uniformly distributed data. In this article, we explored multiple implementations in Python, including basic bucket sorting, loop-based sorting, recursive sorting, dynamic bucket counts, and integer handling.

For beginners, practicing Bucket Sort strengthens understanding of arrays, loops, recursion, and data organization strategies. By experimenting with different inputs and bucket strategies, you can gain a solid foundation in algorithmic thinking and prepare for more advanced sorting techniques.

Share this article

Twitter LinkedIn Facebook