Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // program to implement Bucket sort algorithm in c++
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <cmath>
- using namespace std;
- // function to display the list of elements
- void displayList(vector<int> elementList){
- for(int index = 0; index < elementList.size(); index++) {
- cout << elementList[index] << " ";
- }
- }
- // function to print all the bucket contents
- void displayBuckets(vector< vector<int> > Buckets){
- vector<int> temp;
- for(int index = 0; index<10; index++){
- if(Buckets[index].size()) {
- cout<<"Bucket "<<index<<" : ";
- displayList(Buckets[index]);
- cout<<endl;
- }
- }
- }
- // function to merge the buckets into a vector
- vector <int> joinBuckets(vector< vector<int> > Buckets){
- vector<int> temp, myList;
- for(int index = 0; index<10; index++){
- temp = Buckets[index];
- for(int index2 = 0; index2 < temp.size(); index2++){
- myList.push_back(temp[index2]);
- }
- }
- return myList;
- }
- // method that sorts the list
- vector<int> bucket_sort(vector<int> myList, int length){
- // finding the max element
- int maxElement = (int) *(max_element(myList.begin(), myList.end()));
- // couting the number of digits in the max element
- int digits = 0;
- while (maxElement != 0){
- maxElement = maxElement / 10;
- digits += 1;
- }
- // raising divisor by number of digits
- int divisor = 10;
- long d = divisor;
- vector < vector<int> > Buckets;
- vector <int> temp;
- // loop while divisor does not become 0
- while (divisor < pow(d,digits+1)){
- // initializing Buckets as 10 empty list
- Buckets.clear();
- temp.clear();
- for(int index = 0; index<10; index++){
- Buckets.push_back(temp);
- }
- int element, rem, pos;
- // iterating over the list
- for(int index = 0; index < length; index++){
- element = myList[index];
- // finding the bucket where the element need to be inserted
- rem = element % divisor;
- pos = rem / (divisor/10);
- // print(element, divisor, rem, pos)
- Buckets[pos].push_back(element);
- }
- cout<<"\nAfter dividing by "<<divisor<<" the buckets are : "<<endl;
- displayBuckets(Buckets);
- // divide divisor by 10
- divisor = divisor * 10;
- myList.clear();
- myList = joinBuckets(Buckets);
- // print(myList)
- }
- return myList;
- }
- int main(){
- vector<int> myList;
- cout<<"Program to implement counting sort algorithm in C++"<<endl;
- int length, element;
- cout<<"Enter the number of Elements to be sorted : ";
- cin>>length;
- cout<<"Enter the elements to be sorted : ";
- for(int index = 0; index < length; index++){
- cin>>element;
- myList.push_back(element);
- }
- cout<<"\nThe list of elements before sorting is : "<<endl;;
- displayList(myList);
- vector<int> sortedList = bucket_sort(myList, length);
- cout<<"\nThe sorted list is : "<<endl;
- displayList(sortedList);
- }
Add Comment
Please, Sign In to add comment