Programmazione Avanzata Java e C
Lezione 28:
Algoritmi di ordinamento
18/12/2015 22:07
Algoritmi di ordinamento
Selection sort
Bubble sort
Insertion sort
Quick sort
http://it.wikipedia.org/wiki/File:Sorting_quicksort_anim.gif
Siti su internet:
http://people.cs.ubc.ca/~harrison/Java/sorting-demo.html
http://www.sorting-algorithms.com/
Lezione 14
18/12/2015 22:07
2
Altre considerazioni sugli algoritmi
Per qualunque problema computabile esistono infiniti
algoritmi risolutivi
Complessità computazionale degli algoritmi
Il costo può essere valutato in relazione a diversi
parametri, ad es.


Tempo di calcolo occorrente (complessità temporale)
Occupazione di memoria (complessità spaziale)
Ottimizzare rispetto a un parametro in genere significa
spendere rispetto ad un altro
La rapidità di calcolo è sempre un fattore
importantissimo nella determinazione della bontà di un
algoritmo
Lezione 14
18/12/2015 22:07
3
Tempo di calcolo
Ogni algoritmo è caratterizzato da un suo tempo di
calcolo che determina il tempo necessario affinché tale
algoritmo venga completamente eseguito.
Le prestazioni di un algoritmo sono in qualche modo
proporzionali alla quantità di dati da elaborare e quindi
alla quantità di istruzioni da eseguire
Il numero di istruzioni da eseguire non fornisce sempre
un’indicazione utile, è un buon metodo di valutazione
ma approssimativo e non assoluto.
Lezione 14
18/12/2015 22:07
4
esempio
Tempo di calcolo proporzionale a:




Lezione 14
1 per azzerare il primo elemento di un vettore di N elementi
N per sommare 1 a tutti gli elementi di un vettore di N
elementi
N2 per eseguire due cicli for intrecciati
for(i=0; i<N; i++)
for(j=0; j<N; j++)
…
Log2N ad ogni iterazione la dimensione del vettore da
considerare si dimezza
18/12/2015 22:07
5
Ad esempio:
Insertion sort usa la minima quantità di memoria
indispensabile, ma è lento
Quicksort è veloce, ma usa molta più memoria. Perché?

Lezione 14
Perché, essendo ricorsivo, occorre creare molte istanze della
funzione. Se le cose non sono fatte bene può addirittura
“esplodere” e richiedere una profondità di ricorsione pari al
numero di elementi del vettore.
18/12/2015 22:07
6
Considerazioni sugli algoritmi di
ordinamento
 Bubble sort

effettua all’incirca N2/2 confronti ed N2/2 scambi, sia
in media che nel caso peggiore
 Selection sort


Lezione 14
effettua all’incirca N2/2 confronti ed N scambi
per ogni i da 1 a N -1 c’è uno scambio ed N-i
confronti per un totale di N-1 scambi e (N-1)+(N-2)
+…+2+1=N(N-1)/2 indipendentemente dai dati in
ingresso. L’aggiornamento della variabile min
dipende dai dati in ingresso nel caso peggiore il
numero è quadratico, mediamente NlogN
18/12/2015 22:07
7
Considerazioni sugli algoritmi di
ordinamento
Insertion sort

effettua in media N2/4 confronti ed N2/4 spostamenti (mezzi
scambi), il doppio nel caso peggiore. La complessità diventa
lineare nel caso di vettore quasi ordinato. Se il vettore è già
ordinato non vengono effettuati scambi e il numero di
confronti è pari agli elementi del vettore stesso
 Quick sort


Lezione 14
effettua in media 2NlogN confronti ed NlogN scambi, esegue
N2/2 confronti nel caso peggiore, con sempre circa NlogN
scambi
(se si esegue l’algoritmo su un vettore di N elementi già
ordinato, l’algoritmo richiamerà se stesso N volte con vettori
di dimensioni decrescenti di un’unità)
18/12/2015 22:07
8
Tempi di esecuzione: esempio
Tempi di ordinamento di un vettore contenente tutte le parole
del file DIVINA_COMMEDIA.TXT:
 Bubble sort
7,62 s
 Bubble sort ottimizzato
7,51 s
 Selection sort
2,99 s
 Insertion sort
1.94 s
 Quick sort
0.01 s
Lezione 14
18/12/2015 22:07
9