A simple implementation of Bucket Sort, using insertion sort to sort bucket elements.

#include <iostream>

#include <cassert>

#include <algorithm>

#include <vector>

#include <algorithm>

#include <vector>

template<class FwdIt, class compare = std::less<>>

void insertionSort(FwdIt begin, FwdIt end, compare cmp = compare{})

{

for (auto it = begin; it != end; ++it)

{

auto const insertion = std::upper_bound(begin, it, *it, cmp);

std::rotate(insertion, it, std::next(it));

assert(std::is_sorted(begin, std::next(it), cmp));

}

}

void bucketSort(float arr[], int N)

{

std::vector<std::vector<float>> arrBucket(N); // Created N empty buckets

/* Segregating array elements in different buckets*/

for (int i = 0; i < N; ++i)

{

int bucketIndx = N * arr[i];

arrBucket[bucketIndx].push_back(arr[i]);

}

for (int i = 0; i < N; ++i)

insertionSort(arrBucket[i].begin(), arrBucket[i].end()); // Sorting elements in each Buckets

{

std::vector<std::vector<float>> arrBucket(N); // Created N empty buckets

/* Segregating array elements in different buckets*/

for (int i = 0; i < N; ++i)

{

int bucketIndx = N * arr[i];

arrBucket[bucketIndx].push_back(arr[i]);

}

for (int i = 0; i < N; ++i)

insertionSort(arrBucket[i].begin(), arrBucket[i].end()); // Sorting elements in each Buckets

/* Concatenating all buckets in one final array */

int index = 0;

for (int i = 0; i < N; ++i)

{

for (int j = 0; j < arrBucket[i].size(); ++j)

arr[index++] = arrBucket[i][j];

}

}

int main()

{

float arr[] = {0.68, 0.01, 0.98, 0.23, 0.34};

bucketSort(arr, 5);

for (int i = 0; i < 5; ++i)

std::cout << arr[i] << " ";

return 0;

}

{

float arr[] = {0.68, 0.01, 0.98, 0.23, 0.34};

bucketSort(arr, 5);

for (int i = 0; i < 5; ++i)

std::cout << arr[i] << " ";

return 0;

}

## Comments