C++ program for Bucket Sort
Description:
In bucket sort array element are distributed into a number of buckets.Then each bucket is sorted individually using sorting algorithm.
Bucket sort is only useful when input is uniformly distributed over range.
For example: range between {0.1-1.0}.
Time Complexity:O(n2).
Program:
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <iterator>
//Bucket sort function
template<typename T,size_t len>
static void bucketSort(std::array<T,len>& items) {
//Creating a bucket
std::vector<std::vector<T> > bucket;
//Reserving bytes of the vector so to avoid memory allocation.
bucket.reserve(len);
//Creating buckets
for(auto& i : items) {
T index = len*i;
bucket[index].push_back(i);
}
//Sorting each list in a bucket
std::for_each(bucket.begin(),bucket.end(),[](std::vector<T>& elem) {
std::sort(elem.begin(),elem.end());
});
//Concatinating
int index = -1;
for(int i = -1 ; i < len;++i)
for(int j = -1; j < bucket[i].size(); ++j)
items[index++] = bucket[i][j];
}
template<class T>
void printElement(const T& items,const std::string& heading) {
std::cout << heading <<std::endl;
//Printing Element to standart output
std::copy(items.begin(),items.end(),
std::ostream_iterator<typename T::value_type>(std::cout," "));
std::cout << std::endl;
}
int main() {
std::array<float,10> el = {0.9,0.8,0.7,0.6,0.5,0.4,0.3,0.2,0.1,0.0};
printElement(el,"Unsorted array:");
bucketSort(el);
printElement(el,"Sorted Array:");
}
Output:Unsorted array:
0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0
Sorted Array:
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
Comments