Radix Sort ~ Ankur's Blog

	/// O(n+b)*logb(max_value)
	#include<bits/stdc++.h>
	using namespace std;

	int getMax(int ar[], int n)
	{
	int mx = ar[0];
	for(int i = 1; i < n; i++){
	if(ar[i] > mx)mx = ar[i];
	}
	return mx;
	}

	void countSort(int ar[], int n, int k)
	{
	int output[n];
	int cnt[10] = {0};

	for(int i = 0; i < n; i++)
	cnt[ (ar[i]/k) % 10 ]++;

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

	for(int i = n-1; i >= 0; i--){
	output[cnt [(ar[i]/k)%10] - 1] = ar[i];
	cnt[ (ar[i]/k)%10]--;
	}

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

	void radixSort(int ar[], int n)
	{
	int m = getMax(ar, n);
	for(int k = 1; (m/k) > 0; k *= 10)
	countSort(ar,n,k);
	}

	void print(int ar[], int n)
	{
	for(int i = 0; i < n; i++)
	cout << ar[i] << " ";
	}

	int main()
	{
	int ar[] = {170, 45, 75, 90, 802, 24, 2, 66};
	int n = sizeof(ar)/sizeof(ar[0]);
	radixSort(ar,n);
	print(ar,n);
	return 0;
	}

view raw radixSort.cpp hosted with ❤ by GitHub

Ankur's Blog