#include <bits/stdc++.h>
using namespace std;

void radixSort(int *a, int arraySize){
	vector<int> mybucket[10];
	int i,j,maxVal = 0,digitPosition=1;
    for(i = 0; i < arraySize; i++){
	    if(a[i] > maxVal)
	        maxVal = a[i];
	}
	int p =1;
	char str[20];
	sprintf( str,"%d",maxVal);
	
    while( p <= strlen(str)){
        for(i = 0; i < arraySize; i++)
            mybucket[(a[i]/digitPosition)%10].push_back(a[i]);
        int k = 0;
        cout<<"\nIteration"<<p<<"\n";
        for( i = 9;i>=0;i--){
        	cout<<"Bucket"<<i<<"[";
        	for(j=0;j<mybucket[i].size();j++){
        		a[k++] = mybucket[i][j];
        		cout<<a[k-1]<<",";
        	}
        	cout<<"]\n";
        	mybucket[i].clear();
        }
        digitPosition *= 10;
        p+=1;
    }
}

int main() {
	int *a = new int[20];
	cout<<"I/P\n[ ";
	for( int i =0;i<20;i++){
		a[i] = random()%100;
		cout<<a[i]<<",";
	}
	cout<<"]\n";
	radixSort(a,20);
	cout<<"\nO/P\n[ ";
	for(int i=0;i<20;i++){
		cout<<a[i]<<",";
	}
	cout<<"]";
	return 0;
}