1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli...
-
Upload
sebastiana-bertoni -
Category
Documents
-
view
234 -
download
2
Transcript of 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli...
![Page 1: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/1.jpg)
1
Algoritmi di ordinamento
Selection Sort Quick Sort Lower bound alla complessità degli
algoritmi di ordinamento
![Page 2: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/2.jpg)
2
Selection Sort
L’elemento minimo viene messo in posizione 0
Si itera il procedimento sulle posizioni successive
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];}
}
![Page 3: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/3.jpg)
3
Selection Sort/2
Versione ricorsiva
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) ;
![Page 4: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/4.jpg)
4
Selection Sort/3
Ordinamento del vettore di interi {5, 2, 3, 8, 1}
![Page 5: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/5.jpg)
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 ?
![Page 6: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/6.jpg)
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à)
![Page 7: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/7.jpg)
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)
![Page 8: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/8.jpg)
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
![Page 9: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/9.jpg)
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
![Page 10: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/10.jpg)
11
Quick Sort 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);
}}
![Page 11: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/11.jpg)
12
Quick Sort/2
Array
subarray1 subarray2
< bound
>= bound
< bound1
>= bound2>= bound1
< bound2
![Page 12: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/12.jpg)
13
Partizionamentodell’array [8 5 4 7 6 1 6 3 8 12 10]con quicksort
![Page 13: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/13.jpg)
14
Partizionamentodell’array [8 5 4 7 6 1 6 3 8 12 10]con quicksort
![Page 14: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/14.jpg)
15
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++; /* 1 */
} /* End while */
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);
}
![Page 15: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/15.jpg)
16
Quick Sort/4 void quicksort(Comparable[] data) {
if (data.length < 2)
return;
int max = 0;
/* Trova max. e mettilo alla fine; serve per evitare che lower cresca oltre la dim. dell’ array (non è detto che accada ma può succedere) */
for (int i = 1; i < data.length; i++)
if (data[max].compareTo(data[i]) < 0)
max = i;
swap(data, data.length-1, max); // largest el is now in its
quicksort(data, 0, data.length-2); // final position;
}
![Page 16: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/16.jpg)
17
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
![Page 17: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/17.jpg)
18
Quick Sort – Caso peggiore
L’elemento di pivot è sempre il minimoCosto = O(n-1+n-2+...+2+1) = O(n2)
Array
Array
Array
n-1
n-2
2
1
n-1 volten-2
No. confrontiper sotto-array
![Page 18: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/18.jpg)
19
Quick Sort – Caso migliore
Arrayn-1
n/2-1
2
1
log n+1 volten/4-1
No. confrontiper sotto-array
)1(log2
24
42
2log
0
nnn
n
nn
nnn
n
ii
iCosto =
n potenza di 2 per semplicità
![Page 19: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/19.jpg)
20
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
![Page 20: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/20.jpg)
21
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
![Page 21: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/21.jpg)
22
Alberi di decisione
Un albero di decisione rappresenta i confronti eseguiti da un algoritmo su un dato input
Ogni foglia corrisponde ad una delle possibili permutazioni
a1:a2
a2:a3 a1:a3
a1:a3a2:a3a1,a2,a3
a1,a3,a2 a3,a1,a2
a2,a1,a3
a2,a3,a1 a3,a2,a1
<
<
>
>
< >
< >
< >
Albero di decisione perInsertion Sort sull’insieme{a1, a2, a3}
![Page 22: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/22.jpg)
23
Alberi di decisione/2
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
a1:a2
a2:a3 a1:a3
a1:a3a2:a3a1,a2,a3
a1,a3,a2 a3,a1,a2
a2,a1,a3
a2,a3,a1 a3,a2,a1
<
<
>
>
< >
< >
< >
Albero di decisione perInsertion Sort sull’insieme{a1, a2, a3}
![Page 23: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/23.jpg)
24
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
![Page 24: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/24.jpg)
25
Dimostrazione teorema
1. Un albero di decisione è binario2. Albero binario di altezza h non ha più di 2h foglie
1=21-1
2= 22-1
4= 23-1
2h-1
1
2
3
h
3. Dobbiamo avere: 2h-1 > No. foglie = n!4. h-1 > log(n!)
![Page 25: 1 Algoritmi di ordinamento r Selection Sort r Quick Sort r Lower bound alla complessità degli algoritmi di ordinamento.](https://reader035.fdocumenti.com/reader035/viewer/2022081502/5542eb57497959361e8c1986/html5/thumbnails/25.jpg)
26
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