1
Elementi di Informatica 1
Algoritmi di ordinamento
• Basilare in molteplici applicazioni
• Esempio importante di algoritmi diversi per risolvere lo stesso problema
• Metodi di ordinamento interni: i dati risiedono nella memoria centrale (in un vettore; campo chiave)
• Confronto basato sull'efficienza
Elementi di Informatica 2
Selectionsort
• Ordinamento per selezione
• Si sceglie il minimo del vettore e lo si scambia con la posizione corretta
• Complessità: O(n
2)
• I due cicli vengono sempre eseguiti, indipendentemente dalla configurazione dei dati
Elementi di Informatica 3
Bubblesort
• Basato sulla considerazione che:
ei≤ ei+1
• Confronta coppie adiacenti e eventualmente le scambia
• Dopo una scansione completa l'elemento minore (o maggiore) è nella posizione corretta
• Termina quando sono terminati gli scambi (se è già ordinato serve solo un passo per la verifica)
• Complessità: O(n2)
Elementi di Informatica 4
Mergesort
• Basato sulla fusione (merge) di due vettori ordinati:
– la fusione ha complessità O(n)
• E' intrinsecamente ricorsivo
• Vettore iterativamente diviso in 2 parti:
– ordinamento e fusione
• Complessità O(n log
2n)
Elementi di Informatica 5
Mergesort
• Indipendente dalla configurazione in ingresso
• La ricorsione incrementa la complessità della gestione:
– è consigliabile usare un programma non- ricorsivo
• Per ogni programma ricorsivo esiste un programma non-ricorsivo più efficiente
Elementi di Informatica 6
Quicksort
• Si sceglie un elemento pivot e si suddivide il vettore in due: uno con el. minori, l'altro con el. maggiori o uguali del pivot
• Si procede iterativamente fino a vettori di 1 solo elemento
• La suddivisione ha complessità O(n)
• La complessità della parte ricorsiva
dipende dalla scelta del pivot
2
Elementi di Informatica 7
Quicksort
• Scegliendo come pivot l'elemento min o max, la complessità diventa O(n
2)
• Scegliendo come pivot l'elemento centrale, la complessità è O(n log
2n)
• Il caso peggiore succede raramente
• E' più probabile il caso migliore
• E' usato per la semplicità e l'efficienza
Elementi di Informatica 8
Limite inferiore della complessità
• Si considerano algoritmi la cui operazione fondamentale è il confronto tra elementi
• Problema:
– è ricondotto alla ricerca di una specifica permutazione di n oggetti
– esistono n! permutazioni diverse – tutte le permutazioni sono candidate – ogni passo dell'algoritmo serve per eliminare
dei candidati
Elementi di Informatica 9
Esempio
• La ricerca è rappresentabile
graficamente con un albero binario:
– la radice rappresenta tutte le permutazioni – ogni confronto suddivide le permutazioni
• La profondità dell'albero determina il numero massimo di confronti nel caso peggiore
Elementi di Informatica 10
Esempio
• Ordinare {a1, a2, a3}
• Albero di risoluzione
– 3! = 6 permutazioni (6 foglie) – albero con profondità 3
Elementi di Informatica 11
• L'albero deve avere n! foglie
• In generale un albero binario con profondità i ha al più 2
ifoglie
• Quindi per avere n! foglie, l'albero deve avere profondità p = log(n!)
p = log(n!) ~ log(n/e)n =n log(n) - n log(e) = O(n log(n))
• Il limite inferiore alla complessità è O(n log(n))
Limite inferiore della complessità
Elementi di Informatica 12
Binsort
• Fin'ora gli algoritmi erano basati su operazioni di confronto
• Il binsort utilizza operazioni di indirizzamento con indici
• Sfrutta la conoscenza dell'intervallo di
variabilità delle chiavi
3
Elementi di Informatica 13
Binsort
• Si suppone che gli n elementi del vettore abbiano chiavi [1..n]
• Si scandisce un vettore e si spostano gli elementi in un altro
• Ha complessità O(n)
Elementi di Informatica 14
Binsort
• Caso di più chiavi uguali:
– utilizzo di una lista
– al termine le liste vengono concatenate
• Complessità:
– inserimento O(n) – concatenazione O(n) – totale O(n)
Elementi di Informatica 15
Binsort
• E' il più efficiente se:
– si utilizzano chiavi numeriche
– l'intervallo di variabilità delle chiavi è noto – è possibile effettuare indirizzamenti con
indici
Elementi di Informatica 16
Considerazioni
sulla scelta di un algoritmo
• Le caratteristiche di un algoritmo sono:
– semplice, per facilitarne la comprensione, programmazione, e correzione
– efficiente, cioè richiede una quantità limitata di risorse per l'esecuzione
• Le due caratteristiche si riferiscono a:
– costo umano – costo di esecuzione
Elementi di Informatica 17
Considerazioni
sulla scelta di un algoritmo
• Non esistono regole per la scelta ottima
• Generalmente però:
– si sceglie la prima regola quando si deve eseguire poche volte su insiemi ridotti di dati – si sceglie la seconda se il programma viene
eseguito un grande numero di volte su insiemi estesi di dati
Elementi di Informatica 18
Considerazioni
• Implementazione efficiente dell'algoritmo
– sono state considerate solo le complessità – sono state eliminate le costanti moltiplicative• Per scegliere l'implementazione migliore è necessario considerare tutto
– ad esempio, gli algoritmi ricorsivi sono generalmente molto pesanti