Soluzione dell' HomeWork3aa0203

Vedi anche: HomeWork3aa0203, DomandeHomework3aa0203, RisultatiHomework3aa0203

/*
    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;
}

-- AndreaSterbini - 13 Nov 2002