Counting Sort ~ Ankur's Blog

	/// O(n+k)-(input+range)
	#include<bits/stdc++.h>
	using namespace std;
	#define N 255

	void countSort(char ar[])
	{
	char output[strlen(ar)];

	int cnt[N + 1], i;
	memset(cnt,0,sizeof(cnt));

	for(int i = 0; ar[i]; i++)
	++cnt[ar[i]];

	for(int i = 1; i <= N; i++)
	cnt[i] += cnt[i-1];

	for(int i = 0; ar[i]; i++){
	output[cnt[ar[i]] - 1] = ar[i];
	--cnt[ar[i]];
	}

	for(int i = 0; ar[i]; i++)
	ar[i] = output[i];
	}

	int main()
	{
	char ar[] = "thankstogeeksforgeeks";
	countSort(ar);
	cout << ar << endl;
	return 0;
	}

view raw countingSort1.cpp hosted with ❤ by GitHub

	/// its work negative number also
	#include<bits/stdc++.h>
	using namespace std;

	void countSort(vector<int>& ar)
	{
	// cout << "Enter--------\n";
	int mx = *max_element(ar.begin(), ar.end());
	int mn = *min_element(ar.begin(), ar.end());
	// cout << mx << " "<<mn << endl;
	int N = mx - mn + 1;
	//cout << N << endl;

	vector<int> cnt(N), output(ar.size());

	for(int i = 0; i < ar.size(); i++){
	// cout << ar[i] - mn << " "<< ar[i] << " "<<mn<<endl;
	cnt[ ar[i] - mn ]++;
	}

	for(int i = 1; i <= cnt.size(); i++)
	cnt[i] += cnt[i-1];

	for(int i = ar.size() - 1; i >= 0; i--){
	output[ cnt[ar[i] - mn] - 1] = ar[i];
	cnt[ar[i] - mn]--;
	}

	for(int i = 0; i < ar.size(); i++)
	ar[i] = output[i];
	}

	void print(vector<int>& v)
	{
	for(int i = 0; i < v.size(); i++)
	cout << v[i]<< " ";
	cout << endl;
	}

	int main()
	{
	vector<int> ar = {-5, -10, 0, -3, 8, 5, -1, 10};
	countSort(ar);
	print(ar);
	return 0;
	}

view raw countingsort.cpp hosted with ❤ by GitHub

Ankur's Blog