/*
	 HomeWork3: bucket-sort
	 Usiamo le seguenti strutture dati:
	 - vettore contenente i valori da ordinare
	 - matrice per eseguire le passate
	 - vettore di 10 elementi che tiene il conto di quanti sono inseriti in ciascuna riga della matrice
*/

#include <stdio.h>
#include <limits.h>
 
/* numero di valori in input */
#define SIZE 50
/* i valori vengono considerati come numeri in base 10 */
#define RANGE 10
 
/*
	esegue una passata per la potenza data
	- trasferisce da vettore a matrice
	- rimette nel vettore
	- azzera il vettore che conta quanti numeri sono inseriti in ciascuna riga della matrice
	- torna il valore
		'1' se tutti i valori sono minori della potenza corrente
		'0' se ce n'e' uno maggiore o uguale
*/
int passata(int valori[SIZE], int matrice[RANGE][SIZE], int potenza)
{
	int inseriti[RANGE] = { 0 };	/* numero di elementi inseriti in ciascuna riga della matrice */
	int tuttiminori = 1;		/* indicatore che tutti i valori sono minori della potenza */
	int cifra = 0;			/* cifra corrente */
	int i, j, k;

	/* azzero il numero di numeri inseriti in ciascuna riga*/
	for (i=0 ; i < RANGE ; i++)
		inseriti[i] = 0;

	/* facciamo una passata */
	for (i=0 ; i<SIZE ; i++) {
		/* calcolo la cifra corrente del valore corrente*/
		cifra = (valori[i] / potenza) % 10;
		/* inserisco il valore nella riga giusta ed incremento il conteggio degli elementi presenti */
		matrice[cifra][inseriti[cifra]++] = valori[i];
		/* se il valore corrente è maggiore della prossima potenza devo ripetere la passata */
		/* faccio il confronto dopo un cast a double per essere sicuro di gestire numeri vicino a INT_MAX */
		if (valori[i] >= (double)potenza*10)
			tuttiminori = 0;
	}

	/* ricopiamo i valori indietro nel vettore di appoggio nell'ordine giusto */
	k = 0;
	for (i=0 ; i < RANGE ; i++)
		for (j=0 ; j < inseriti[i] ; j++)
			valori[k++] = matrice[i][j];

	/* faccio sapere se serve un'altra passata */
	return tuttiminori;
}

/* programma principale */
int main(int argc, char * argv[]) {
	 /* dichiarazioni */
	 int matrice[RANGE][SIZE] = { 0 };	/* matrice */
	 int valori[SIZE] = { 0 };		/* vettore di appoggio dei valori */
	 int i;
	 int potenza = 1;			/* potenza di dieci corrente */
	 int passate = 1;			/* conteggio delle passate */
	 int tuttiminori = 0;		/* indicatore=1 se tutti i valori sono minori della prossima potenza */

	 /* dati personali */
	 printf("Andrea\nSterbini\n02\n02\n1961\nsterbini@dsi.uniroma1NOSPAM.it\n");

	 /* lettura degli input */
	 for (i=0 ; i<SIZE ; i++)
		  scanf("%d",&valori[i]);

	 /* ciclo per le varie potenze di 10 crescenti */
	 while (tuttiminori==0) {
		 tuttiminori = passata(valori, matrice, potenza);
		 potenza *= 10;
		 passate ++;
	 }

	 /* output dei valori (che sono tornati nel vettore di appoggio) */
	 for (i=0 ; i<SIZE ; i++)
		  printf("%d\n",valori[i]);

	 /* stampa del numero di passate */
	 printf("%d\n",passate);

	 return 0;
}