vakho

Counting Sort

Jun 10th, 2012
152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <ctime>
  5.  
  6. using namespace std;
  7.  
  8. void countingSort(const vector<int> &a, vector<int> &b)//-> include <vector>;
  9. {
  10.     int k = *max_element(a.begin(), a.end());//-> include <algorithm>;
  11.     k++;
  12.  
  13.     vector<int> c(k);
  14.  
  15.     for (int i = 0; i < a.size(); i++)
  16.         c[ a[i] ]++;
  17.     for (int i = 1; i < k; i++)
  18.         c[i] += c[i - 1];
  19.  
  20.     for (int i = (a.size() - 1); i >= 0; i--)
  21.     {
  22.         b[ c[ a[i] ] - 1 ] = a[i];
  23.         c[ a[i] ]--;
  24.     };
  25. };
  26.  
  27. int main()
  28. {
  29.     system("COLOR F0");
  30.     srand( time(NULL) );//-> include <ctime>
  31.  
  32.     vector<int> a;
  33.     for (int i = 0; i < 5; i++)
  34.     {
  35.         int num = rand()% 30 + 1;//-> from 1 to 30;
  36.         a.push_back(num);
  37.     };
  38.  
  39.     vector<int> b(a.size());
  40.  
  41.     for (int i = 0; i < a.size(); i++)
  42.         cout << " a [ " << i << " ]\t= " << a[i] << endl;
  43.     cout << endl;
  44.  
  45.     countingSort(a, b);
  46.  
  47.     for (int i = 0; i < b.size(); i++)
  48.         cout << " b [ " << i << " ]\t= " << b[i] << endl;
  49.     cout << endl;
  50.  
  51.     system("PAUSE");
  52.     return (0);
  53. };
Advertisement
Add Comment
Please, Sign In to add comment