HomeWork3aa0203 < Programmazione1/AA0506/PZ

Tags: view all tags

---++ Esercizio numero 3
Vedi anche DomandeHomework3aa0203, SoluzioneHomework3aa0203, RisultatiHomework3aa0203.
----
%TOC%
----
---+++ Bucket Sort
Implementare l'algoritmo di *bucket-sort* completo da applicare a *50 input interi e non negativi*.

---+++ Come funziona
L'algoritmo *bucket-sort* ordina un vettore di *N* numeri usando una (o due) matrici di appoggio di *10* righe ed *N* colonne.
   * per ciascuna cifra (potenza di 10) dei numeri a partire dalle unità
      * per ciascun numero in input *x* (in cui chiameremo la cifra corrente *y*)
         * si inserisce *x* nella riga con indice *y*
   * dopo la prima passata i numeri si troveranno suddivisi tra le diverse righe della matrice in base alla cifra corrente (partendo dalle unità)
   * si ripete la passata:
      * considerando la successiva cifra decimale (le decine, poi le centinaia ...)
      * leggendo i numeri dalla matrice in ordine da sinistra verso destra e dall'alto in basso
      * inserendo i numeri in una seconda matrice secondo le stesse regole della prima passata
   * se nella passata appena passata :-) nessun numero è maggiore della potenza di 10 che stiamo esaminando
      * si termina l'esecuzione
         * i numeri ordinati si trovano nella prima riga (indice 0)
      * altrimenti si ripete la passata scambiando le due matrici e passando alla prossima cifra (potenza di 10)

---+++ Esempio di funzionamento
Supponiamo di dover ordinare i 7 numeri *45 18 90 1 6 83 16*. 
Inseriamoli in qest'ordine in una matrice a seconda della loro cifra delle *unità*:
| *cifra* | *Matrice dopo la prima passata (unità)* |||||||
| *0* |  90  | | | | | | |
| *1* |  1  | | | | | | |
| *2* | | | | | | | |
| *3* |  83  | | | | | | |
| *4* | | | | | | | |
| *5* |  45  | | | | | | |
| *6* |  6  |  16  | | | | | |
| *7* | | | | | | | |
| *8* |  18  | | | | | | |
| *9* | | | | | | | |

Nella seconda passata i numeri vengono letti dalla matrice nell'ordine *90 1 83 45 6 16 18* 
ed inseriti in una seconda matrice esaminando le *decine* ed ottenendo:
| *cifra* | *Matrice dopo la seconda passata (decine)* |||||||
| *0* |  1  |  6  | | | | | |
| *1* |  16  |  18  | | | | | |
| *2* | | | | | | | |
| *3* | | | | | | | |
| *4* |  45  | | | | | | |
| *5* | | | | | | | |
| *6* | | | | | | | |
| *7* | | | | | | | |
| *8* |  83  | | | | | | |
| *9* |  90  | | | | | | |

Nella terza passata i numeri vengono letti dalla matrice nell'ordine *1 6 16 18 45 83 90* ed inseriti tutti nella riga *0* perchè la cifra corrente (*centinaia*) è sempre 0.
| *cifra* | *Matrice dopo la terza passata (centinaia)* |||||||
| *0* |  1  |  6  |  16  |  18  |  45  |  83  |  90  |
| *1* | | | | | | | |
| *2* | | | | | | | |
| *3* | | | | | | | |
| *4* | | | | | | | |
| *5* | | | | | | | |
| *6* | | | | | | | |
| *7* | | | | | | | |
| *8* | | | | | | | |
| *9* | | | | | | | |

A questo punto il programma termina perchè tutti i numeri sono minori di *100* (la cifra corrente).

---+++ Input
L'input è dato da 50 numeri su righe separate.
   * interi
   * non negativi
   * sono permesse le ripetizioni
   * il valore massimo è sicuramente minore di *INT_MAX*, la costante contenuta in *limits.h* e che indica il massimo numero rappresentabile da un *int* e che vale *2147483647* sul mio Linux.
Per esempio:
<verbatim>
900
45
89
... (altri 45 numeri interi non negativi, anche con ripetizioni)
3
12
</verbatim>

---+++ Output
Come al solito le prime sei righe dell'output debbono indicare i vostri dati personali (vedi HomeWork1aa0203 ed HomeWork2aa0203).

*State attenti a non inserire inutili prompt o \n*

Le righe successive debbono elencare, un numero per riga, i 50 numeri nell'ordine in cui si trovano sulla riga 0 della matrice.

La 57° riga dell'output indica il numero di _passate_ eseguite riempiendo la matrice:
   * ogni passata corrisponde all'analisi di una delle cifre dei numeri
   * va contata anche la passata finale che porta tutti i numeri nella riga 0 

Nell'[[#Esempio_di_funzionamento][esempio di funzionamento]] riportato sopra il numero di passate è *3*.

---+++ Suggerimento
Se volete usare meno memoria e semplificare il vostro programma:
   * usate una sola matrice di appoggio di *10 x N* elementi
   * più il vettore che contiene gli *N* valori da ordinare
   * ricopiate i valori dalla matrice al vettore nell'ordine spiegato prima di passare alla prossima cifra

---+++ Consegna
L'esercizio va consegnato *entro le ore 24 di domenica 10 Novembre* esclusivamente usando la form http://twiki.dsi.uniroma1.it/~andrea/consegna.html

-- Users.AndreaSterbini - 04 Nov 2002

<!--
   * Set ALLOWTOPICCHANGE = Users.DocentiProg1Group
-->