Untitled

#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() {
	// your code goes here
	
	int n;
	cin >> n;
	
	int arr[n];
	for(int i=0; i<n; i++) cin >> arr[i];
	
	printArray(arr, n);
	radixSort(arr, n);
	printArray(arr, n);
	return 0;
}