Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.2 kB
50
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 max, int min){
	
	int range = max - min + 1;
	int * farr = new int[range];
	
	// 2nd step - find these frequencies
	for(int i=0; i<n; i++){
		int idx = arr[i] - min;
		farr[idx]++;
	}
	
	// 3rd step - cummulative sum
	for(int i=1; i<range; i++){
		farr[i] = farr[i] + farr[i-1];
	}
	
	int * ans = new int[n];
	for(int i=n-1; i>=0; i--){
		
		int val = arr[i];
		int pos = farr[val - min];
		int idx = pos - 1;
		ans[idx] = val;
		farr[val - min]--;
	}
	
	for(int i=0; i<n; i++) arr[i] = ans[i];
	
}

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);
	countSort(arr, n);
	printArray(arr, n);
	return 0;
}