Bucket Sort in C and C++

Here you will get program for bucket sort in C and C++.

In bucket sort algorithm the array elements are distributed into a number of buckets. Then each bucket sorted individually either using any other sorting algorithm or by recursively applying bucket sort.

Take example shown in below image.

Elements are distributed among buckets

Then, elements are sorted within each bucket

Below is the program to implement this algorithm. In this program it is assumed that the array elements are between 0 to 10.

Program for Bucket Sort in C

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

struct bucket 
{
    int count;
    int* value;
};

int compareIntegers(const void* first, const void* second)
{
    int x = *((int*)first), y =  *((int*)second);
    if (x == y)
    {
        return 0;
    }
    else if (x < y)
    {
        return -1;
    }
    else
    {
        return 1;
    }
}

void bucketSort(int array[],int n)
{
    struct bucket buckets[3];
    int i, j, k;
    for (i = 0; i < 3; i++)
    {
        buckets[i].count = 0;
        buckets[i].value = (int*)malloc(sizeof(int) * n);
    }
    
    for (i = 0; i < n; i++)
    {
        if (array[i] < 0)
        {
            buckets[0].value[buckets[0].count++] = array[i];
        }
        else if (array[i] > 10)
        {
            buckets[2].value[buckets[2].count++] = array[i];
        }
        else
        {
            buckets[1].value[buckets[1].count++] = array[i];
        }
    }
    for (k = 0, i = 0; i < 3; i++)
    {
        // now using quicksort to sort the elements of buckets
        qsort(buckets[i].value, buckets[i].count, sizeof(int), &compareIntegers);
        for (j = 0; j < buckets[i].count; j++)
        {
            array[k + j] = buckets[i].value[j];
        }
        k += buckets[i].count;
        free(buckets[i].value);
    }
}

int main(char *arg[]) {

    int array[100] = { 5, -34, 10, 1, -42, 123, 2, 395, 5, 4, 1234, 7 };
    int i = 12,j,k,n;

    n=i;
    printf("Before Sorting\n");
    for (j = 0; j<i; j++)
    {
        printf("%d ", array[j]);
    }

    bucketSort(array, n); 
    printf("\n After Sorting\n");
    for (k = 0; k<i; k++)
        printf("%d ", array[k]);   


    return 0;
}

Output

Before Sorting
5 -34 10 1 -42 123 2 395 5 4 1234 7
After Sorting
-42 -34 1 2 4 5 5 7 10 123 395 1234

Program for Bucket Sort in C++

#include <iostream>
#include <algorithm>
#include <vector> //used for the sake of simplicity
using namespace std;
 

void bucketSort(float arr[], int n)
{
    vector<float> b[n];
    
    for (int i=0; i<n; i++)
    {
       int x = n*arr[i];
       b[x].push_back(arr[i]);
    }
 
    for (int i=0; i<n; i++)
       sort(b[i].begin(), b[i].end());
 
    int index = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < b[i].size(); j++)
          arr[index++] = b[i][j];
}
 
int main()
{
    float arr[] = {0.235, 0.101, 0.476, 0.7645, 0.15, 0.142};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Before Sorting\n";
    for (int i=0; i<n; i++)
    cout << arr[i] << " ";
    
    bucketSort(arr, n);
    
    cout << "\nAfter Sorting \n";
    for (int i=0; i<n; i++)
       cout << arr[i] << " ";
    return 0;
}

Output

Before Sorting
0.235 0.101 0.476 0.7645 0.15 0.142
After Sorting
0.101 0.142 0.15 0.235 0.476 0.7645