Bucket Sort

Bucket Sort is a sorting algorithm that works by distributing elements into several groups called buckets.

Each bucket is then sorted individually, either using another sorting algorithm (like Insertion Sort) or recursively using Bucket Sort itself. After sorting, all the buckets are merged together to form the final sorted array.

Bucket Sort is a distribution sort that works by

Dividing elements into several buckets (groups).
Sorting each bucket individually (often using insertion sort or any other sorting algorithm).
Concatenating all sorted buckets to get the final sorted array.

It is efficient when the input is uniformly distributed over a range.

How Bucket Sort Works?

Create buckets based on the range of input values.
Distribute the elements of the array into appropriate buckets.
Sort each bucket individually.
Concatenate all buckets in order.

What is the Range?

The range of a dataset is the difference between the maximum and minimum values in the data.
Range = Maximum value − Minimum value

Why Calculate Range in Bucket Sort?

To divide the data into buckets, you need to know the span of the values.
Each bucket covers an equal portion of this range.
This helps you decide which bucket an element belongs to.

How to Calculate Range?

Given an array [42, 23, 56, 19, 30, 75, 61]

Find the minimum: min = 19
Find the maximum: max = 75
Calculate range: Range = 75 − 19 = 56

How to Use Range for Bucketing?

If you want to create k buckets.
Bucket size (interval) = Range / K
Example: For 5 buckets, Bucket size = 56 / 5 = 11.2

Assigning Elements to Buckets

For each element x:
Bucket index = (x−min) / Bucket size
Make sure the bucket index does not exceed k−1.

Example with the Array Above

min = 19, range = 56, buckets = 5, bucket size = 11.2
For element 42, Bucket index = (42−19) / 11.2 = 2.01 = 2
So 42 goes to bucket index 2.

Numerical: Bucket Sort

Input Array: [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]

Assume all elements are in the range [0, 1).

Step 1: Create Buckets

Let’s create 5 buckets: bucket[0], bucket[1], bucket[2], bucket[3], bucket[4]

Each bucket represents a sub-range.

Bucket	Range
bucket[0]	[0.0, 0.2)
bucket[1]	[0.2, 0.4)
bucket[2]	[0.4, 0.6)
bucket[3]	[0.6, 0.8)
bucket[4]	[0.8, 1.0)

Step 2: Distribute Elements into Buckets

0.42 → bucket[2]  
0.32 → bucket[1]  
0.23 → bucket[1]  
0.52 → bucket[2]  
0.25 → bucket[1]  
0.47 → bucket[2]  
0.51 → bucket[2]

Buckets after distribution

bucket[0]: []
bucket[1]: [0.32, 0.23, 0.25]
bucket[2]: [0.42, 0.52, 0.47, 0.51]
bucket[3]: []
bucket[4]: []

Step 3: Sort Each Bucket

Using Insertion Sort or any other simple sort.

bucket[1]: [0.23, 0.25, 0.32]  
bucket[2]: [0.42, 0.47, 0.51, 0.52]

Step 4: Concatenate Buckets

Final sorted array: [0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]

When to Use Bucket Sort?

Use Bucket Sort when

Data is uniformly distributed.
Input is in a known fixed range (like [0, 1) for floating-point numbers).
A stable and fast sorting algorithm is needed for large datasets.

Algorithm for Bucket Sort (Ascending)

Step-by-Step Algorithm

Initialize Buckets
- Create k empty buckets (lists or arrays).
Distribute Elements
- For each element x in the input array:
  - Compute the appropriate bucket index using a formula like:
    index = floor(x * k) (for values in [0, 1))
  - Place x into the corresponding bucket.
Sort Individual Buckets
- Sort each non-empty bucket using an internal sorting algorithm (e.g., Insertion Sort).
Concatenate Buckets
- Go through each bucket in order and copy the sorted elements back into the original array.

Pseudocode

BucketSort(arr[], n)
1. Create n empty buckets (B[0], B[1], ..., B[n-1])
2. for i = 0 to n-1 do
       index = floor(n * arr[i]) // Assuming arr[i] in [0, 1)
       B[index].append(arr[i])
3. for i = 0 to n-1 do
       sort(B[i])  // Can use Insertion Sort or any other algorithm
4. Concatenate all buckets into arr[]

Time and Space Complexity

Case	Time Complexity
Best	O(n + k)
Average	O(n + k + n²/k)
Worst	O(n²) (if all elements go into one bucket)

n = number of elements
k = number of buckets

Space Complexity: O(n + k)

Stable: Yes (if stable sort used in buckets)

Advantages of Bucket Sort

Fast for Uniformly Distributed Data: Works very efficiently when input data is uniformly distributed over a known range.

Stable Sorting : It can be made stable if the sorting algorithm used inside each bucket is stable (like Insertion Sort).

Parallelizable: Each bucket can be sorted independently, which makes it suitable for parallel processing.

Efficient for Floating-Point Numbers: It handles floating-point numbers well, especially those in the range [0, 1).

Better Time Complexity in Best Case: Can perform better than O(n log n) in the best case (almost linear time O(n + k)).

Disadvantages of Bucket Sort

Not Suitable for All Data Distributions: Performance degrades if data is not uniformly distributed many elements may fall into a few buckets.

Extra Space Required: Needs additional space for buckets not an in-place sort.

Difficult to Choose Number of Buckets: Choosing the optimal number and size of buckets is non-trivial and often depends on the input.

Not Ideal for Small Inputs: Overhead of creating buckets and sorting them may not be worth it for small datasets.

Worst Case Can Be O(n²): If all elements go into one bucket, it behaves like Insertion Sort or whatever inner sort you use.

C Program for Bucket Sort

#include <stdio.h>
#include <stdlib.h>

#define N 7 // number of elements
#define BUCKETS 5

// Insertion sort for each bucket
void insertionSort(float arr[], int n) {
    for (int i = 1; i < n; i++) {
        float key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

void bucketSort(float arr[]) {
    float buckets[BUCKETS][N];
    int bucketCount[BUCKETS] = {0};

    // Put elements into buckets
    for (int i = 0; i < N; i++) {
        int bi = arr[i] * BUCKETS; // bucket index
        buckets[bi][bucketCount[bi]++] = arr[i];
    }

    // Sort individual buckets
    for (int i = 0; i < BUCKETS; i++) {
        insertionSort(buckets[i], bucketCount[i]);
    }

    // Concatenate buckets
    int index = 0;
    for (int i = 0; i < BUCKETS; i++) {
        for (int j = 0; j < bucketCount[i]; j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

void printArray(float arr[]) {
    for (int i = 0; i < N; i++) {
        printf("%.2f ", arr[i]);
    }
    printf("\n");
}

int main() {
    float arr[N] = {0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51};
    printf("Original array:\n");
    printArray(arr);

    bucketSort(arr);

    printf("Sorted array:\n");
    printArray(arr);
    return 0;
}

Numerical Questions for Bucket Sort

Sort the following list using Bucket Sort [0.42, 0.32, 0.23, 0.52, 0.25]
Apply Bucket Sort on [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12]
Sort this list using Bucket Sort and show each step [0.91, 0.67, 0.45, 0.12, 0.29, 0.10, 0.99]
Use Bucket Sort with 4 buckets to sort [0.33, 0.57, 0.18, 0.24, 0.47, 0.62, 0.05]
Sort the array using Bucket Sort and also show which sorting method you used inside each bucket [0.13, 0.17, 0.89, 0.76, 0.35, 0.22, 0.94]
Sort the following using Bucket Sort. Assume the elements are uniformly distributed. Use insertion sort inside each bucket [0.95, 0.42, 0.66, 0.10, 0.05, 0.25, 0.75, 0.34, 0.58]
Given the array [0.19, 0.87, 0.45, 0.93, 0.37, 0.12],
1. Distribute them into 6 buckets
2. Sort each bucket
3. Merge and show the final sorted array
Design your own dataset of 10 values between 0 and 1, and apply Bucket Sort using 5 buckets. Show each step clearly.
Given the array [88, 45, 12, 67, 34, 23, 90, 51]
1. Calculate the range.
2. Divide the array into 5 buckets.
3. Assign each element to the correct bucket.
4. Sort each bucket and write the final sorted array.
Sort the following array using Bucket Sort with 4 buckets [88, 45, 12, 67, 34, 23, 90, 51]
1. Find the range.
2. Calculate bucket size.
3. Show bucket assignments.
4. Show sorted buckets and the final sorted list.
Given this array, create 3 buckets and sort using Bucket Sort [120, 150, 180, 90, 60, 30]
1. Calculate range.
2. Calculate bucket intervals.
3. Assign numbers to buckets.
4. Sort and combine.
Apply Bucket Sort on [1000, 1500, 1200, 1100, 1800, 1600, 1300]
1. Use 4 buckets.
2. Show each step including range, bucket size, bucket content, and sorted output.
For the array [15, 3, 27, 18, 10, 5, 33, 21]
1. Use 6 buckets.
2. Assign values to buckets.
3. Sort buckets and merge the results.

Menu