#include <iostream>

#include <vector>

#include <math.h>

using namespace std;



void printSorted(int x[], int length);



vector < vector <int> > buckets;



void radixSort(int x[],int length)

{

    int temp;

    int m=0;

    //Begin Radix Sort

    for(int i=0;i<7;i++)

      {    //Determine which bucket each element should enter

        for(int j=0;j<length;j++)

         {

            temp=(int)((x[j])/pow(10,i))%10;

            buckets[temp].push_back((x[j]));

         }

        //Transfer results of buckets back into main array

        for(int k=0;k<10;k++)

            {

            for(int l=0;l<buckets[k].size();l++)

              {

                x[m]=buckets[k][l];

                m++;

               }

            //Clear previous bucket

            buckets[k].clear();

            }

        m=0;

    }

    buckets.clear();

    printSorted(x,length);

}

void printSorted(int x[], int length){

    for(int i=0;i<length;i++)

        cout<<x[i]<<endl;

}



int main(){

    int testcases;

    cout<<"How many numbers do you want to sort? "<<endl;

    cin>>testcases;

    int input[testcases];

    buckets.resize(10);

    int number;

    cout<<"Put the numbers: "<<endl;

    for(int i=0;i<testcases;i++){

        cout<<i<<". number: ";

        cin>>number;

        input[i]=number;

    }

    cout<<endl;

    cout<<"I print sorted numbers:"<<endl;

    radixSort(input,testcases);

    return 0;

}