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

Edit | Attach | Watch | Print version | History: r8 < r7 < r6 < r5 < r4 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r8 - 2003-09-30 - AndreaSterbini






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback