Esercizio numero 3

Vedi anche DomandeHomework3aa0203, SoluzioneHomework3aa0203, RisultatiHomework3aa0203.

---

---

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:

900
45
89
... (altri 45 numeri interi non negativi, anche con ripetizioni)
3
12

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 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

-- AndreaSterbini - 04 Nov 2002