Lezione 2
Lezione 2
Algoritmi di Ordinamento

In questa seconda lezione implementeremo e studieremo il comportamento di alcuni algoritmi di ordinamento

ESERCIZIO 2.0 - Selection sort:
È dato un file /home/comune/labTNDS_aa1011_materiale/lezione2/data.txt che contiene 1E6 valori.
Il programma riempie un array di N posizioni con i primi N valori letti dal file e ordina il vettore usando l'algoritmo selection sort.
N è passato al programma da riga di comando.
Si richiede di stampare su file l'array prima (before.dat) e dopo (after.dat) l'ordinamento.
Provare ad eseguire il codice variando N, da qualche centinaia a qualche decina di migliaia e valutarne il
tempo di esecuzione.

Brevi Richiami
Struttura del programma

Passaggio di input da linea di comando

Tempo di esecuzione

ESERCIZIO 2.1 - Bubble sort (da consegnare):
Come nell'Esercizio 2.0, ordinare gli elementi di un array (caricato dal file di input, N elementi).
Per l'ordinamento, utilizzare l'algoritmo Bubble sort invece che Selection sort.
Si richiede di stampare l'array prima e dopo l'ordinamento, variando N e valutando il tempo di esecuzione.

Brevi richiami
L'algoritmo Bubble sort

ESERCIZIO 2.2 - Stabilità degli algoritmi di sorting (da consegnare):
Ordinare il vettore usando usando una volta selection sort ed un altra bubble sort tenendo conto solo
delle decine, secondo questo criterio:

int(v[i])/10 > int(v[i+1])/10

Verificare se l'ordine di unità e decimali rimane invariato rispetto al vettore di partenza.

Ci si accorgerà che l'algoritmo di bubble sort è stabile, mentre quello di selection sort non lo è.
Questo significa che se due elementi sono equivalenti dal punto di vista del criterio di ordinamento
scelto, nel caso del bubble sort vengono lasciati nell'ordine in cui compaiono nel vettore di partenza,
mentre nel caso del selection sort questo non è garantito.

Brevi richiami
Cast
Back to Home Page