Bucket sort is a comparison sorting algorithm. It scans elements and put these into different buckets. Each bucket is sorted individually using a sorting algorithm of your choice. It constructs n buckets into which the input is partitioned. It reduces the processing time at the expense of the storage space, these buckets use.

## 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;
}
```