Implement Bucket Sort using C++

Implement a Bucket Sort method using C++

You can use bucket sort if the input values are distributed uniformly over a given range. Mostly, the bucket sort is used to sort floating-point numbers in the range [0,1]

Needless to say, the recursive implementation of the bucket sorting algorithm uses the bucket sorting to sort the bucket’s data.

To keep things simple, we will use the sort() function from the algorithm library to sort bucket’s data while using the liner approach to implement the algorithm.

So, let’s create a function that takes an array, its length and sort the array.

void bucketSort(float arr[], int n)
 {
 // code goes here. 
 }

Now, create n number of empty buckets using vectors in C++. A vector is used to implement a dynamic array. A vector stores the elements in the same way array does, but array is a fixed-size data structure, whereas vector can allocate the memory at run time.

vector<float> b[n];

This declares a vector of floating-point type.

The next step is to put numbers in buckets.

  for (int i=0; i<n; i++)
  {
       int bi = n*arr[i];
       b[bi].push_back(arr[i]);
    }

Once, you have the numbers in the respective buckets, it’s time to sort the data in each bucket.

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

By default, sort() function sorts an array in ascending order. 

In the end, concatenate all buckets to get the sorted list. 

int index = 0;
    for (int i = 0; i < n; i++)
        for ( int j = 0; j < (signed)b[i].size(); j++)
          arr[index++] = b[i][j];

Putting all of this together:

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


void bucketSort(float arr[], int n)
{
    // Create n number of empty buckets
    vector<float> b[n];

    // put data in their prospective buckets
    for (int i=0; i<n; i++)
    {
       int bi = n*arr[i];
       b[bi].push_back(arr[i]);
    }

    // Sort the array using the default sort() function from algorithm library
    for (int i=0; i<n; i++)
       sort(b[i].begin(), b[i].end());

    // Concatenate all buckets in
    int index = 0;
    for (int i = 0; i < n; i++)
        for ( int j = 0; j < (signed)b[i].size(); j++)
          arr[index++] = b[i][j];
}

Now call the function above from the main function

int main()
{
    float data[] = {0.8 , 0.5 , 0.6 , 0.1 , 0.6 , 0.3 };
    int len = sizeof(data)/sizeof(data[0]);

    cout << "Unsorted array is :";
    for (int i=0; i<len; i++)
       cout << data[i] << " ";

    bucketSort(data, len);

    cout << endl<<"Sorted array is   :";
    for (int i=0; i<len; i++)
       cout << data[i] << " ";

    cout<<endl;
    return 0;
}

Related Articles