Bucket Sort

Today, we are going to explore another elegant and efficient sorting technique: Bucket Sort.

Sorting lies at the heart of data processing, whether you’re ranking exam scores, organizing financial transactions, or arranging sensor readings.

Among all sorting methods, Bucket Sort stands out for its simplicity and speed on uniformly distributed data.
Unlike comparison-heavy algorithms, Bucket Sort distributes elements into buckets, sorts each bucket individually, and then concatenates the results.

This can yield linear time complexity in favorable cases.

List of Contents

• Introduction to Bucket Sort

• Core concept and working principle

• Steps of the Bucket Sort algorithm

• Example walkthrough

• Implementation code in C++, Java, and C

• Time and space complexity

• Advantages and disadvantages

Introduction

Bucket Sort is a distribution sort that works by:

• Dividing input data into a finite number of buckets (or bins).

• Distributing the elements into these buckets based on a hashing or mapping function.

• Sorting each bucket individually (often using insertion sort or another simple algorithm).

• Concatenating all sorted buckets into the final sorted list.

It is particularly effective when data is uniformly distributed over a range.

Core Concept and Working of Bucket Sort

Bucket Sort leverages the idea that if you can pre-classify elements into ranges (buckets), you can sort each range more quickly.

How it works:

• Determine the range of input data.

• Create a set of empty buckets covering this range.

• Place each element into its appropriate bucket.

• Sort each bucket individually.

• Concatenate the contents of all buckets.

This approach reduces the overall number of comparisons and can approach O(n) time when the data is distributed evenly.

Steps of the Bucket Sort Algorithm

• Find the maximum and minimum values to establish the range.

• Create k empty buckets.

• Distribute each input element into its bucket based on its value.

• Sort each bucket (often using insertion sort).

• Concatenate all sorted buckets to produce the final sorted array.

Example of Bucket Sort

Let’s sort this list:

[0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]

Assume 5 buckets for [0,1):

1) Create buckets:

• 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)

2) Distribute:

• 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: []

3) Sort each bucket:

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

4) Concatenate:

[0.23,0.25,0.32,0.42,0.47,0.51,0.52]

Sorted list complete!

C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void bucketSort(vector<float>& arr) {
    int n = arr.size();
    vector<vector<float>> buckets(n);

    for (float num : arr) {
        int idx = n * num;
        buckets[idx].push_back(num);
    }

    for (int i = 0; i < n; i++)
        sort(buckets[i].begin(), buckets[i].end());

    int k = 0;
    for (int i = 0; i < n; i++)
        for (float num : buckets[i])
            arr[k++] = num;
}

int main() {
    vector<float> arr = {0.42,0.32,0.23,0.52,0.25,0.47,0.51};
    bucketSort(arr);
    for (float num : arr)
        cout << num << " ";
    return 0;
}

Java Implementation

import java.util.*;

class BucketSort {
    @SuppressWarnings("unchecked")
    public static void bucketSort(float[] arr) {
        int n = arr.length;
        List<Float>[] buckets = (List<Float>[]) new ArrayList[n];

        for (int i = 0; i < n; i++)
            buckets[i] = new ArrayList<>();

        for (float num : arr) {
            int idx = (int)(n * num);
            if (idx == n) idx = n - 1; // Handle num == 1.0
            buckets[idx].add(num);
        }

        for (int i = 0; i < n; i++)
            Collections.sort(buckets[i]);

        int k = 0;
        for (List<Float> bucket : buckets)
            for (float num : bucket)
                arr[k++] = num;
    }

    public static void main(String[] args) {
        float[] arr = {0.42f, 0.32f, 0.23f, 0.52f, 0.25f, 0.47f, 0.51f};
        bucketSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

C Implementation

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

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[], int n) {
    float buckets[n][n];
    int bucketCount[n];
    for (int i = 0; i < n; i++)
        bucketCount[i] = 0;

    for (int i = 0; i < n; i++) {
        int idx = n * arr[i];
        buckets[idx][bucketCount[idx]++] = arr[i];
    }

    for (int i = 0; i < n; i++)
        insertionSort(buckets[i], bucketCount[i]);

    int k = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < bucketCount[i]; j++)
            arr[k++] = buckets[i][j];
}

int main() {
    float arr[] = {0.42,0.32,0.23,0.52,0.25,0.47,0.51};
    int n = sizeof(arr)/sizeof(arr[0]);
    bucketSort(arr, n);

    for (int i = 0; i < n; i++)
        printf("%.2f ", arr[i]);
    return 0;
}

Time and Space Complexity

• Time Complexity:

  • Average Case: O(n + k)

  • Worst Case: O(n²) (if all elements land in one bucket)

• Space Complexity:

O(n + k) (space for buckets)

Advantages

• Very fast when data is uniformly distributed.

• Linear time complexity in the best and average cases.

• Simple concept and easy to implement.

• Can be combined with other algorithms for sorting buckets.

Disadvantages

• Inefficient for non-uniform distributions (e.g., clustered data).

• Requires additional space for buckets.

• Worst-case performance can degrade to O(n²).

• Works best when input is known to be in a specific range (e.g., [0,1)).

Key Points:

• Bucket Sort is excellent for sorting floating-point numbers in a fixed interval.

• It is not comparison-based but relies on distribution.

• Combining with insertion sort or quicksort in buckets yields optimal results.

For more topics....

Click here

Till then...

Happy Coding!!!