Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Author - Fueanta
- // Counting Sort - O(N)
- // Last Modified - 13 Oct, 17
- #include <iostream>
- using namespace std;
- void fillArray(int*, int);
- void printArr(int*, int, string);
- void CountingSort(int*, int*, int, int, int);
- int main(void)
- {
- int size = 0, _maxP = 0, _maxN = 0;
- cout << "Size of the array: "; cin >> size;
- int *arr = new int[size], *sorted = new int[size];
- fillArray(arr, size);
- printArr(arr, size, "[unsorted]");
- cout << "\nMax positive value among given data: "; cin >> _maxP;
- cout << "\nMax negative value among given data: "; cin >> _maxN;
- CountingSort(arr, sorted, size, _maxP, _maxN);
- printArr(sorted, size, "[sorted]");
- return 0;
- }
- void fillArray(int array[], int size)
- {
- cout << "\nTaking array input:\n";
- for (int i = 0; i < size; ++i)
- {
- cout << "Element " << (i + 1) << ": ";
- cin >> array[i];
- }
- cout << "Array Input has been taken.\n";
- }
- void printArr(int arr[], int n, string array_name)
- {
- cout << "\nPrinting " << array_name << " array:\n[ ";
- for (int i = 0; i < n - 1; ++i)
- {
- cout << arr[i] << " | ";
- }
- cout << arr[n - 1] << " ]\n";
- }
- void CountingSort(int* unsorted, int* sorted, int _size, int pos_max, int neg_max)
- {
- int _maxP = pos_max + 1; // size required to hold (0 to max -1) and max itself
- int _maxN = (neg_max * (-1));
- int pos_counter[_maxP] = {0}; // making all the components zero in pos_counter array
- int neg_counter[_maxN] = {0};
- /*
- Now, let's count the occurrences of the data values in the unsorted array
- */
- for (int i = 0; i < _size; ++i)
- {
- int value = unsorted[i];
- if (value >= 0) pos_counter[value]++;
- else neg_counter[(value * (-1)) - 1]++;
- }
- // printArr(pos_counter, _maxP, "pos counter debug");
- // printArr(neg_counter, _maxN, "neg counter debug");
- /*
- Now, lets't count the total of the occurrences of the data values where,
- -> array[current_index] = occurrence of self-index + occurrences of previous indexes
- */
- for (int i = 1; i < _maxP; ++i)
- {
- pos_counter[i] += pos_counter[i - 1];
- }
- for (int i = 1; i < _maxN; ++i)
- {
- neg_counter[i] += neg_counter[i - 1];
- }
- int total_neg = neg_counter[_maxN - 1]; // required to sort negative data
- // printArr(pos_counter, _maxP, "pos counter debug");
- // printArr(neg_counter, _maxN, "neg counter debug");
- /*
- Now, let's take an empty array named "sorted" and then put all the sorted data
- for (int i = 0; i < _size; ++i)
- {
- sorted[i] = 0;
- }
- */
- /*
- now, let's do the sort thing with the modified algorithm
- */
- for (int i = (_size - 1); i > -1; --i)
- {
- int value = unsorted[i];
- if (value > -1)
- {
- sorted[(pos_counter[value]--) + total_neg - 1 ] = unsorted[i];
- }
- else
- {
- value *= -1;
- value -= 1;
- // cout << unsorted[i] << " gets into index no " << (neg_counter[_maxN - 1] - neg_counter[value]) << endl;
- sorted[total_neg - neg_counter[value]--] = unsorted[i];
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement