m2skills

Bucket sort c++

Oct 13th, 2017
21
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.14 KB | None | 0 0
  1. // program to implement Bucket sort algorithm in c++
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <cmath>
  6. using namespace std;
  7.  
  8. // function to display the list of elements
  9. void displayList(vector<int> elementList){
  10.     for(int index = 0; index < elementList.size(); index++) {
  11.         cout << elementList[index] << " ";
  12.     }
  13. }
  14.  
  15. // function to print all the bucket contents
  16. void displayBuckets(vector< vector<int> > Buckets){
  17.     vector<int> temp;
  18.     for(int index = 0; index<10; index++){
  19.         if(Buckets[index].size()) {
  20.             cout<<"Bucket "<<index<<" : ";
  21.             displayList(Buckets[index]);
  22.             cout<<endl;
  23.         }
  24.     }
  25. }
  26.  
  27. // function to merge the buckets into a vector
  28. vector <int> joinBuckets(vector< vector<int> > Buckets){
  29.     vector<int> temp, myList;
  30.     for(int index = 0; index<10; index++){
  31.         temp = Buckets[index];
  32.         for(int index2 = 0; index2 < temp.size(); index2++){
  33.             myList.push_back(temp[index2]);
  34.         }
  35.     }
  36.     return myList;
  37. }
  38.  
  39. // method that sorts the list
  40. vector<int> bucket_sort(vector<int> myList, int length){
  41.  
  42.     // finding the max element
  43.     int maxElement = (int) *(max_element(myList.begin(), myList.end()));
  44.  
  45.     // couting the number of digits in the max element
  46.     int digits = 0;
  47.     while (maxElement != 0){
  48.         maxElement = maxElement / 10;
  49.         digits += 1;
  50.     }
  51.  
  52.     // raising divisor by number of digits
  53.     int divisor = 10;
  54.     long d = divisor;
  55.     vector < vector<int> > Buckets;
  56.     vector <int> temp;
  57.     // loop while divisor does not become 0
  58.     while (divisor < pow(d,digits+1)){
  59.         // initializing Buckets as 10 empty list
  60.  
  61.         Buckets.clear();
  62.         temp.clear();
  63.         for(int index = 0; index<10; index++){
  64.             Buckets.push_back(temp);
  65.         }
  66.         int element, rem, pos;
  67.         // iterating over the list
  68.         for(int index = 0; index < length; index++){
  69.  
  70.             element = myList[index];
  71.             // finding the bucket where the element need to be inserted
  72.             rem = element % divisor;
  73.             pos = rem / (divisor/10);
  74.  
  75.             // print(element, divisor, rem, pos)
  76.             Buckets[pos].push_back(element);
  77.         }
  78.  
  79.         cout<<"\nAfter dividing by "<<divisor<<" the buckets are : "<<endl;
  80.         displayBuckets(Buckets);
  81.         // divide divisor by 10
  82.         divisor = divisor * 10;
  83.         myList.clear();
  84.         myList = joinBuckets(Buckets);
  85.         // print(myList)
  86.     }
  87.     return myList;
  88. }
  89.  
  90. int main(){
  91.  
  92.     vector<int> myList;
  93.  
  94.     cout<<"Program to implement counting sort algorithm in C++"<<endl;
  95.     int length, element;
  96.     cout<<"Enter the number of Elements to be sorted : ";
  97.     cin>>length;
  98.     cout<<"Enter the elements to be sorted : ";
  99.     for(int index = 0; index < length; index++){
  100.         cin>>element;
  101.         myList.push_back(element);
  102.     }
  103.  
  104.     cout<<"\nThe list of elements before sorting is : "<<endl;;
  105.     displayList(myList);
  106.  
  107.     vector<int> sortedList = bucket_sort(myList, length);
  108.  
  109.     cout<<"\nThe sorted list is : "<<endl;
  110.     displayList(sortedList);
  111. }
Add Comment
Please, Sign In to add comment