Advertisement
fueanta

Counting Sort in C++

Oct 13th, 2017
226
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.21 KB | None | 0 0
  1. // Author - Fueanta
  2. // Counting Sort - O(N)
  3. // Last Modified - 13 Oct, 17
  4.  
  5. #include <iostream>
  6.  
  7. using namespace std;
  8.  
  9. void fillArray(int*, int);
  10. void printArr(int*, int, string);
  11. void CountingSort(int*, int*, int, int, int);
  12.  
  13. int main(void)
  14. {
  15.     int size = 0, _maxP = 0, _maxN = 0;
  16.     cout << "Size of the array: "; cin >> size;
  17.     int *arr = new int[size], *sorted = new int[size];
  18.  
  19.     fillArray(arr, size);
  20.     printArr(arr, size, "[unsorted]");
  21.  
  22.     cout << "\nMax positive value among given data: "; cin >> _maxP;
  23.     cout << "\nMax negative value among given data: "; cin >> _maxN;
  24.  
  25.     CountingSort(arr, sorted, size, _maxP, _maxN);
  26.     printArr(sorted, size, "[sorted]");
  27.     return 0;
  28. }
  29.  
  30. void fillArray(int array[], int size)
  31. {
  32.     cout << "\nTaking array input:\n";
  33.     for (int i = 0; i < size; ++i)
  34.     {
  35.         cout << "Element " << (i + 1) << ": ";
  36.         cin >> array[i];
  37.     }
  38.     cout << "Array Input has been taken.\n";
  39. }
  40.  
  41. void printArr(int arr[], int n, string array_name)
  42. {
  43.     cout << "\nPrinting " << array_name << " array:\n[ ";
  44.     for (int i = 0; i < n - 1; ++i)
  45.     {
  46.         cout << arr[i] << " | ";
  47.     }
  48.     cout << arr[n - 1] << " ]\n";
  49. }
  50.  
  51. void CountingSort(int* unsorted, int* sorted, int _size, int pos_max, int neg_max)
  52. {
  53.     int _maxP = pos_max + 1; // size required to hold (0 to max -1) and max itself
  54.     int _maxN = (neg_max * (-1));
  55.  
  56.     int pos_counter[_maxP] = {0}; // making all the components zero in pos_counter array
  57.     int neg_counter[_maxN] = {0};
  58.     /*
  59.     Now, let's count the occurrences of the data values in the unsorted array
  60.     */
  61.     for (int i = 0; i < _size; ++i)
  62.     {
  63.         int value = unsorted[i];
  64.         if (value >= 0) pos_counter[value]++;
  65.         else neg_counter[(value * (-1)) - 1]++;
  66.     }
  67.  
  68.     // printArr(pos_counter, _maxP, "pos counter debug");
  69.     // printArr(neg_counter, _maxN, "neg counter debug");
  70.  
  71.     /*
  72.     Now, lets't count the total of the occurrences of the data values where,
  73.     -> array[current_index] = occurrence of self-index + occurrences of previous indexes
  74.     */
  75.     for (int i = 1; i < _maxP; ++i)
  76.     {
  77.         pos_counter[i] += pos_counter[i - 1];
  78.     }
  79.     for (int i = 1; i < _maxN; ++i)
  80.     {
  81.         neg_counter[i] += neg_counter[i - 1];
  82.     }
  83.     int total_neg = neg_counter[_maxN - 1]; // required to sort negative data
  84.  
  85.     // printArr(pos_counter, _maxP, "pos counter debug");
  86.     // printArr(neg_counter, _maxN, "neg counter debug");
  87.  
  88.     /*
  89.     Now, let's take an empty array named "sorted" and then put all the sorted data
  90.     for (int i = 0; i < _size; ++i)
  91.     {
  92.         sorted[i] = 0;
  93.     }
  94.     */
  95.  
  96.     /*
  97.         now, let's do the sort thing with the modified algorithm
  98.      */
  99.     for (int i = (_size - 1); i > -1; --i)
  100.     {
  101.         int value = unsorted[i];
  102.         if (value > -1)
  103.         {
  104.             sorted[(pos_counter[value]--) + total_neg - 1 ] = unsorted[i];
  105.         }
  106.         else
  107.         {
  108.             value *= -1;
  109.             value -= 1;
  110.             // cout << unsorted[i] << " gets into index no " << (neg_counter[_maxN - 1] - neg_counter[value]) << endl;
  111.             sorted[total_neg - neg_counter[value]--] = unsorted[i];
  112.         }
  113.     }
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement