Algoritmi e Strutture Dati
III.
Algoritmi di Ordinamento
1
Algoritmi di ordinamento
 Selection Sort
 Quick Sort
 Lower bound alla complessità degli
algoritmi di ordinamento
asd_library.sorting.SortingAlgorithms
2
Selection Sort
SelectionSort(dati[]) {
for (i=0; i<dati.length-1; i++) {
min = <Seleziona min. in dati[i], …. , dati[dati.length-1]>
<Scambia min con dati[i];
}
}
 L’elemento minimo viene messo in posizione 0
 Si itera il procedimento sulle posizioni
successive
3
Selection Sort/2
SelectionSort(dati[], i) {
min = <Seleziona min. in dati[i], …. , dati[dati.length-1]>
<Scambia min con dati[i];
SelectionSort(dati[], i+1) ;
}
……
SelectionSort(dati[], 0) ;
 Versione ricorsiva
4
Selection Sort/3
Ordinamento del vettore di interi {5, 2, 3, 8, 1}
5
Come ordinare oggetti diversi da numeri
 Ordinare un vettore i cui elementi sono oggetti
complessi. Es. oggetti della classe:
class Persona {
String cognome;
String CF;
public Persona (String cognome, String CF) {
this.cognome = cognome;
this.CF = CF;
}
}
 Come ordinare un array di tali oggetti rispetto al
cognome ?
6
Come ordinare oggetti diversi da numeri/2
 Occorre:
1. Dichiarare che tra gli oggetti della classe (Persona
nell’esempio) è definito un ordinamento
2. Dichiarare rispetto a quale o a quali membri della classe è
definito l’ordinamento (il cognome nel nostro caso)
3. Definire la regola che stabilisce l’ordinamento tra due oggetti
della classe (nel nostro caso: due oggetti di tipo persona sono
ordinati alfabeticamente secondo i rispettivi cognomi)
 In C++ si possono sovraccaricare gli operatori
 In Java si può dichiarare che la classe (Persona)
implementa l’interfaccia Comparable (non è la sola
possibilità)
7
Come ordinare oggetti diversi da numeri/3
 Il passo 1 si traduce così:
class Persona implements Comparable {
……
}
 I passi 2 e 3 consistono nell’implementare l’unico
metodo previsto dall’interfaccia Comparable: int
compareTo(Object o)
 compareTo definisce le regole che stabiliscono
l’ordinamento tra oggetti della classe (nel nostro caso,
l’ordinamento è quello alfabetico sui cognomi)
8
Come ordinare oggetti diversi da numeri/4
 Quindi:
class Persona implements Comparable {
String cognome;
String CF;
public Persona (String cognome, String CF) {
this.cognome = cognome;
this.CF = CF;
}
public int compareTo (Object pers) {
return
cognome.compareTo(((Persona)pers).cognome);
}
}
Nota: occorre fare il cast perché compareTo vuole un Object
9
Selection Sort/4
public void selectionsort(Comparable[] data) {
int i, j, least;
for (i = 0; i < data.length-1; i++) {
for (j = i+1, least = i; j < data.length; j++)
if (data[j].compareTo(data[least]) < 0)
least = j;
swap(data, least, i); /* Scambia gli oggetti in pos. i e least */
}
}
Es.: versione ricorsiva
10
Quick Sort
Disponi l’elemento maggiore in ultima posizione
quicksort(array[]) {
if (array.length>1) {
Scegli bound; /* subarray1 e subarray2 */
while (ci sono elementi in array)
if (generico elemento < bound)
inserisci elemento in subarray1;
else inserisci elemento in subarray2;
quicksort(subarray1);
quicksort(subarray2);
}
}
12
Quick Sort/2
Array
< bound
subarray2
subarray1
>= bound
< bound2
< bound1
>= bound1
>= bound2
13
Partizionamento
dell’array
[8 5 4 7 6 1 6 3 8 12 10]
con quicksort
14
Proprietà di Quicksort
 Un’iterazione termina quando lower supera upper
 data[first+1..upper]: elementi minori o uguali del




pivot
data[upper+1..last]: elementi maggiori del pivot
Si scambia il pivot con l’elemento in posizione
upper
Si chiama ricorsivamente QuickSort su
data[first+1..upper-1] e su data[upper+1..last], se
gli array hanno almeno due elementi
Occorre evitare upper=last, per cui si dispone
l’elemento maggiore in ultima posizione
15
Partizionamento
dell’array
[8 5 4 7 6 1 6 3 8 12 10]
con quicksort
16
Quick Sort/3
void quicksort(Comparable[] data, int first, int last) {
int lower = first + 1, upper = last;
swap(data, first, (first+last)/2); /* Questo serve solo perché così, in pratica è
spesso più veloce */
Comparable bound = data[first];
while( (lower <= upper)){
while(data[lower].compareTo(bound) <= 0)
lower++;
while (bound.compareTo(data[upper]) < 0)
upper--;
if (lower < upper)
swap(data, lower++, upper--);
else lower++;
} /* End while */
17
Quick Sort/4
swap(data, upper, first);
if (first < upper-1) /* se first == upper-1 il sottoarray ha solo 2 elementi ed è
ordinato */
quicksort(data, first, upper-1);
if (upper+1 < last)
quicksort(data, upper+1, last);
}
18
Analisi del Quick Sort
 Costo = O(No. confronti)
 Costo O(n2) nel caso peggiore
 Costo O(n log n) nel caso migliore e medio
 In pratica l’algoritmo è efficiente
 Scelta pivot fondamentale
19
Quick Sort – Caso peggiore
No. confronti
per sotto-array
n-1
n-2
n-2
Array
Array
Array
n-1 volte
2
1
L’elemento di pivot è sempre il minimo
Costo = O(n-1+n-2+...+2+1) = O(n2)
20
Quick Sort – Caso migliore
No. confronti
per sotto-array
n-1
n potenza di 2 per semplicità
Array
n/2-1
n/4-1
log n+1 volte
2
1
Costo
n
n
n logn i n
= n  2  4    n   2 i  n(log n  1)
2
4
n i 0 2
21
Efficienza algoritmi di
ordinamento
 Merge Sort (e Heap Sort): O(n log n)
 Quick Sort, Selection Sort, Insertion Sort: O(n2)
 Quick Sort: O(n log n) nel caso migliore
 Selection Sort: O(n2) in tutti i casi
 Insertion Sort: O(n) nel caso migliore
 Domanda: qual è l’efficienza massima (complessità
minima) ottenibile nel caso peggiore -> Lower bound
22
Ordinamento – limiti inferiori
 Osservazione fondamentale: tutti gli algoritmi




devono confrontare elementi
Dati ai, ak, tre casi possibili: ai < ak, ai > ak, oppure
ai=ak
Si assume per semplicità che tutti gli elementi siano
distinti
Si assume dunque che tutti i confronti abbiano la
forma ai < ak, e il risultato del confronto sia vero o
falso
Nota: se gli elementi possono avere lo stesso valore
allora si considerano solo confronti del tipo ai <= ak
23
Alberi di decisione
Albero di decisione per
Insertion Sort sull’insieme
<
{a1, a2, a3}
<
a1,a2,a3
a1:a2
a2:a3 >
<
a1,a3,a2
>
<
a1:a3
>
a1:a3
a2,a1,a3
a3,a1,a2
>
<
a2:a3
a2,a3,a1
>
a3,a2,a1
 Un albero di decisione rappresenta i confronti
eseguiti da un algoritmo su un dato input
 Ogni foglia corrisponde ad una delle possibili
permutazioni
24
Alberi di decisione/2
Albero di decisione per
Insertion Sort sull’insieme
<
{a1, a2, a3}
<
a1,a2,a3
a1:a2
a2:a3 >
<
a1,a3,a2
>
<
a1:a3
>
a1:a3
a2,a1,a3
a3,a1,a2
>
<
a2,a3,a1
a2:a3
>
a3,a2,a1
 Vi sono n! possibili permutazioni -> l’albero deve contenere n!
foglie
 L’esecuzione di un algoritmo corrisponde ad un cammino
sull’albero di decisione corrispondente all’input considerato
25
Alberi di decisione/3
 Riassumendo:
 Albero binario
 Deve contenere n! foglie
 Il più lungo cammino dalla radice ad una foglia
(altezza) rappresenta il No. confronti che l’algoritmo
deve eseguire nel caso peggiore
 Teorema: qualunque albero di decisione che ordina n
elementi ha altezza Ώ(n log n)
 Corollario: nessun algoritmo di ordinamento ha
complessità migliore di Ώ(n log n)
Nota: esistono algoritmi di ordinamento con complessità
più bassa, ma richiedono informazioni aggiuntive
26
Dimostrazione teorema
1. Un albero di decisione è binario
2. Albero binario di altezza h non ha più di 2h-1 foglie
1
1=21-1
2
2= 22-1
3
4= 23-1
h
2h-1
3. Dobbiamo avere: 2h-1 > No. foglie = n!
4. h-1 > log(n!)
27
Dimostrazione teorema/2
5. n! > (n/e)n (approssimazione di Stirling)
6. h-1 > log(n/e)n = n log(n/e) = n logn – n loge = Ώ(n log
n)
 Corollario: gli algoritmi Merge Sort e Heap Sort
hanno complessità asintotica ottima
28
Il problema della Selezione
 Determinare l’i-esimo elemento più piccolo
di una collezione di n elementi.
 Soluzione banale: ordinare l’insieme di
elementi e determinare l’elemento in
posizione i. Costo: O(n log n).
 E’ possibile determinare l’i-esimo elemento
con costo lineare?
29
Select(i) – Algoritmo dei mediani
1.
2.
3.
4.
5.
Dividi in n/5 gruppi di 5 elementi ciascuno
Determina il mediano di ogni gruppo di 5 elementi
Invoca ricorsivamente Select(n/10) sull’insieme
degli n/5 mediani per determinare m, il mediano
dei mediani
Partiziona gli n elementi nell’insieme A dei k
elementi più piccoli di m, e B degli n-k elementi
>=m
Se i<=k, allora Select (A,i), altrimenti Select (B,ik)
30
Analisi di Select(i)
 Osservazione: Gli insiemi A e B contengono
almeno 3n/10 elementi.
 T(n)<=T(n/5)+T(7n/10)+dn
 Ipotesi: T(n)<=cn
T(n)<=cn/5+7cn/10+dn
= 9cn/10 + dn
<=cn
se c/10>=d
31
Esercizi
Determinare la complessità di QuickSort se ad ogni passo il
mediano degli elementi dell’array è selezionato come pivot
con costo m(n)
2. Determinare un lower bound sul costo della ricerca di un
elemento in una collezione ordinata
1.
3. Si consideri la seguente equazione di ricorrenza
n 1
a
F ( n)  
 F (n  1)  cn n  1
Individuare un algoritmo di ordinamento la cui funzione di
costo temporale è esprimibile tramite la F(n) definita.
Determinare una delimitazione superiore per la funzione F(n)
32