Ordinamento 1

Algoritmi di ordinamento

! Selection Sort

! Quick Sort

! Lower bound alla complessità deglialgoritmi di ordinamento

Ordinamento 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];

}

}

Ordinamento 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) ;

Ordinamento 4

Selection Sort/3

Ordinamento del vettore di interi {5, 2, 3, 8, 1}

Ordinamento 5

Come ordinare oggetti diversi da numeri

! Ordinare un vettore i cui elementi sono oggetticomplessi. 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 alcognome ?

Ordinamento 6

Come ordinare oggetti diversi danumeri/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 dueoggetti della classe (nel nostro caso: due oggetti di tipopersona sono ordinati alfabeticamente secondo i rispettivicognomi)

! In C++ si possono sovraccaricare gli operatori

! In Java si può dichiarare che la classe (Persona)implementa l’interfaccia Comparable (non è la solapossibilità)

Ordinamento 7

Come ordinare oggetti diversi danumeri/3

! Il passo 1 si traduce così:class Persona implements Comparable {

……

}

! I passi 2 e 3 consistono nell’implementare l’unicometodo previsto dall’interfaccia Comparable:

int compareTo(Object o)

! compareTo definisce le regole che stabilisconol’ordinamento tra oggetti della classe (nel nostrocaso, l’ordinamento è quello alfabetico sui cognomi)

Ordinamento 8

Come ordinare oggetti diversi danumeri/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

Ordinamento 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

Ordinamento 10

Selection Sort - Tempo di esecuzione

! Supponiamo che l’array contenga n elementi

! Alla i-esima iterazione occorre trovare il massimo di n-i+1elementi e sono quindi necessari n-i confronti

! Vi sono n-1 cicli

Costo =

! Si osservi che tale costo non dipende dall’ eventualeordinamento parziale dell’array (cfr. Insertion Sort)

! !"

=

"

=

"=="

1

1

1

1 2

)1()(

n

i

n

i

nniin

Ordinamento 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);

}

}

Ordinamento 12

Quick Sort/2

Array

subarray1 subarray2

< bound

>= bound

< bound1

>= bound2>= bound1

< bound2

Ordinamento 13

Partizionamentodell’array [8 5 4 7 6 1 6 3 8 12 10]con quicksort

Ordinamento 14

Partizionamentodell’array [8 5 4 7 6 1 6 3 8 12 10]con quicksort

Ordinamento 15

Quick Sort/3 void quicksort(Comparable[] data, int first, int last) {

int lower = first + 1, upper = last;

swap(data, first, (first+last)/2); /* 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); // Alla fine upper punta sempre a un elemento <= bound

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);

}

Ordinamento 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); // Elemento piu’ grande in posizione finale

quicksort(data, 0, data.length-2);

}

Ordinamento 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

Ordinamento 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 volte

n-2

No. confrontiper sotto-array

Ordinamento 19

Quick Sort – Caso migliore

Arrayn-1

n/2-1

2

1

log n+1 volte

n/4-1

No. confrontiper sotto-array

)1(log2

244

22

log

0

+==++++ !=

nnn

n

nn

nnn

n

i

i

iLCosto =

n potenza di 2 per semplicità

Ordinamento 20

! 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

Efficienza algoritmi di ordinamento

Ordinamento 21

Ordinamento – limiti inferiori

! Osservazione fondamentale: tutti gli algoritmidevono confrontare elementi

! Dati ai, ak, tre casi possibili: ai < ak, ai > ak, oppureai=ak

! Si assume per semplicità che tutti gli elementisiano distinti

! Si assume dunque che tutti i confronti abbiano laforma ai < ak, e il risultato del confronto sia vero ofalso

! Nota: se gli elementi possono avere lo stessovalore allora si considerano solo confronti del tipoai <= ak

Ordinamento 22

Alberi di decisione

! Un albero di decisione rappresenta i confrontieseguiti da un algoritmo su un dato input

! Ogni foglia corrisponde ad una delle possibilipermutazioni

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}

Ordinamento 23

Alberi di decisione/2

! Vi sono n! possibili permutazioni -> l’albero deve conteneren! foglie

! L’esecuzione di un algoritmo corrisponde ad un camminosull’albero di decisione corrispondente all’input considerato

Albero di decisione perInsertion Sort sull’insieme{a1, a2, a3}

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

<

<

>

>

< >

<>

<>

Ordinamento 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 chel’algoritmo deve eseguire nel caso peggiore

! Teorema: qualunque albero di decisione che ordinan elementi ha altezza !(n log n)

! Corollario: nessun algoritmo di ordinamento hacomplessità migliore di !(n log n)

Nota: esistono algoritmi di ordinamento concomplessità più bassa, ma richiedono informazioniaggiuntive

Ordinamento 25

Dimostrazione teorema

1. Un albero di decisione è binario

2. 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!)

Ordinamento 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