/* 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; }
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica |
|