Bucket Sort Algorithm

Introduction to Bucket Sort

Bucket sort is a sorting algorithm that distributes elements of an array into several buckets. Each bucket is then sorted individually, either using a different sorting algorithm or recursively applying the bucket sort algorithm. The elements are then concatenated to get the sorted array. Bucket sort is useful when the input is uniformly distributed over a range.

Step-by-Step Process

Consider an array with the following elements:


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

To sort this array using bucket sort, follow these steps:

  1. Create Buckets: Create an empty bucket for each element in the array.
  2. Distribute Elements: Distribute the elements of the array into the buckets. Each element is placed into a bucket that corresponds to a specific range.
  3. Sort Buckets: Sort each non-empty bucket. You can use any sorting algorithm for this step, such as insertion sort or quicksort.
  4. Concatenate Buckets: Concatenate the sorted buckets to form the final sorted array.

Let's apply these steps to the example array:

  • Create 10 empty buckets: [[], [], [], [], [], [], [], [], [], []]
  • Distribute elements: [[0.12, 0.17, 0.21, 0.23, 0.26], [0.39], [0.68, 0.72, 0.78], [], [], [], [], [], [0.94], []]
  • Sort each bucket: [[0.12, 0.17, 0.21, 0.23, 0.26], [0.39], [0.68, 0.72, 0.78], [], [], [], [], [], [0.94], []]
  • Concatenate buckets: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

Pseudo Code for Bucket Sort

Below is the pseudo code for the bucket sort algorithm:


function bucketSort(array)
    n = length(array)
    create n empty buckets
    for each element in array do
        insert element into corresponding bucket
    for each bucket do
        sort(bucket)
    concatenate all buckets into array
end function

Explanation:

  • Create Buckets: The function starts by creating n empty buckets, where n is the length of the array.
  • Distribute Elements: Each element in the array is distributed into its corresponding bucket based on its value.
  • Sort Buckets: Each bucket is individually sorted using a suitable sorting algorithm.
  • Concatenate Buckets: The sorted buckets are concatenated to form the final sorted array.

Python Program to Implement Bucket Sort

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

def bucket_sort(array):
    bucket = []
    n = len(array)
    for i in range(n):
        bucket.append([])

    for j in array:
        index_b = int(n * j)
        bucket[index_b].append(j)

    for i in range(n):
        bucket[i] = insertion_sort(bucket[i])

    k = 0
    for i in range(n):
        for j in range(len(bucket[i])):
            array[k] = bucket[i][j]
            k += 1
    return array

# Example usage:
array = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
print("Original array:", array)
sorted_array = bucket_sort(array)
print("Sorted array:", sorted_array)  # Output: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

This Python program defines a function to perform bucket sort on an array. The function creates buckets, distributes the elements into the buckets, sorts each bucket using insertion sort, and then concatenates the sorted buckets to get the final sorted array.