#include<iostream>
#include<queue>
#include<ctime>
using namespace std;

void GenerateVector(int *, int);
void PrintVector(int *, int);
void RadixSort(int *, int);


int main(){
	int A[10000],n=5;
	GenerateVector(A,n);
	PrintVector(A,n);
	RadixSort(A,n);
	PrintVector(A,n);
	system("pause");

}

void GenerateVector(int *A, int n)
{
	srand(time(NULL));

	for(int i=0;i<n;i++){
		A[i]=rand()%100;
	}
}

void PrintVector(int *A, int n)
{
	for(int i=0;i<n;i++){
		cout<<A[i]<<" ";
	}
	cout<<endl;
}

void RadixSort(int *A, int n)
{
	queue <int> Q[10];
	for(int p=10;p<=1000;p=10*p){
		//introducem elementele tabloului A in cozile Q dupa cifra considerata.
		for(int i=0;i<n;i++){            
			Q[(A[i]%p)/(p/10)].push(A[i]);
		}
	    
		//golim cozile in tabloul A
		int k=0;
		for(int i=0;i<10;i++){
			while(!Q[i].empty()){
				A[k++]=Q[i].front();
				Q[i].pop();
			}
		}
	}
}