Radix Sorting

QUESTION

Given an array of N integers, you need to print the array after each pass of radix sort. In each pass, you need to sort the array by digits starting from least significant digit to most significant digit.\n\nInput:\nThe first line consists of an integer N denoting the size of array.\nThe next line consists of N space separated integers.\n\nOutput: \nPrint the array after each pass. See the output for clarity.

“TESTCASE_1”: “8\n170 45 75 90 802 24 2 66\n###—###SEPERATOR—###—\n170 90 802 2 24 45 75 66 \n802 2 24 45 66 170 75 90 \n2 24 45 66 75 90 170 802”, “TESTCASE_2”: “10\n65 47 212 89 177 14 345 68 2 684\n###—###SEPERATOR—###—\n212 2 14 684 65 345 47 177 68 89 \n2 212 14 345 47 65 68 177 684 89 \n2 14 47 65 68 89 177 212 345 684”, “TESTCASE_3”: “15\n65 47 212 89 177 14 345 68 2 684 74 852 122 36 842\n###—###SEPERATOR—###—\n212 2 852 122 842 14 684 74 65 345 36 47 177 68 89 \n2 212 14 122 36 842 345 47 852 65 68 74 177 684 89 \n2 14 36 47 65 68 74 89 122 177 212 345 684 842 852”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include <iostream>
#include <math.h>
using namespace std;
 
void sort(int a[], int n, int exp)
{
	int c[100000], i, b[100000], k=9;
	for(i=1;i<=n;i++)
	{
		b[i]=0;
	}
	for(i=1;i<=k;i++)
	{
		c[i]=0;
	}
	for(i=1;i<=n;i++)
	{
		c[(a[i]/exp)%10]++;
	}
	for(i=1;i<=k;i++)
	{
		c[i]=c[i]+c[i-1];
	}
	for(i=n;i>=1;i--)
	{
		b[c[(a[i]/exp)%10]]=a[i];
		c[(a[i]/exp)%10]--;
	}
	for(i=1;i<=n;i++)
	{
		a[i]=b[i];
	}
	for(i=1;i<=n;i++)
	{
	    cout<<a[i]<<" ";
	}
	cout<<endl;
}
void printarray(int arr[], int n)
{
	int i;
	for(i=1;i<=n;i++)
		cout<<arr[i]<<" ";
}
 
 
void radix(int a[], int n)
{
	int i, key=-999999, k=0;
	for(i=1;i<=n;i++)
	{
		if(a[i]>key)
			key=a[i];
	}
	for(i=1;key/i>0;i*=10)
	{
		sort(a, n, i);
	}
}
int main()
{
	int i, n, a[100000], b[100000];
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];b[i]=0;
	}
	radix(a, n);
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro