# Untitled

unknown
plain_text
2 years ago
1.5 kB
33
Indexable
Never
```#include <iostream>
#include <climits>
using namespace std;

void printArray(int * arr, int n){
for(int i=0; i<n; i++) cout << arr[i] << ", ";
cout << endl;
}

void countSortHelper(int * arr, int n, int exp){

// - 287, 39, 48, 56, 785, exp - 1

int * farr = new int[10];

// 2nd step - find these frequencies
for(int i=0; i<n; i++){
int idx = (arr[i] / exp) % 10; // [ 3 to 10]
farr[idx]++;
}

// 3rd step - cummulative sum
for(int i=1; i<10; i++){
farr[i] = farr[i] + farr[i-1];
}

int * ans = new int[n];
for(int i=n-1; i>=0; i--){

int pos = farr[(arr[i] / exp) % 10];
int idx = pos - 1;
ans[idx] = arr[i];
farr[(arr[i] / exp) % 10]--;
}

for(int i=0; i<n; i++) arr[i] = ans[i];

}

void radixSort(int * arr, int n){

// find the maximum value
int maxValue = arr[0];
for(int i=1; i<n; i++){
maxValue = max(maxValue, arr[i]);
}

// count sort call
int exp = 1;
while(exp <= maxValue){

countSortHelper(arr, n, exp); // sort array based on digits
exp = exp * 10;
}
}
// void countSort(int * arr, int n){

// 	// 1st step - finding the range
// 	int maxValue = arr[0], minValue = arr[0];
// 	for(int i=1; i<n; i++){
// 		maxValue = max(maxValue, arr[i]);
// 		minValue = min(minValue, arr[i]);
// 	}

// 	countSortHelper(arr, n, maxValue, minValue);
// }

int main() {