Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl1
Ordinamenti ottimi(nel modello basato su confronti)
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl2
• Usa la tecnica del divide et impera:
1 Divide: dividi l’array a metà
2 Risolvi il sottoproblema ricorsivamente
3 Impera: fondi le due sottosequenze ordinate
MergeSort
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl3
Esempio di esecuzione
7 2 4 5 3 1 5 6
7 2 4 5 3 1 5 6
7 2 4 5 3 1 5 6
7 2 4 5 3 1 5 6
1 2 3 4 5 5 6 7
2 4 5 7 1 3 5 6
2 7 4 5 1 3 5 6
7 2 4 5 3 1 5 6
input
output
Input ed
output delle
chiamate
ricorsive
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl4
• Due array ordinati A e B possono essere fusi rapidamente:– estrai ripetutamente il minimo di A e B e copialo
nell’array di output, finché A oppure B non diventa vuoto
– copia gli elementi dell’array non vuoto alla fine dell’array di output
Procedura Merge
Notazione: dato un array A e due indici x y, denotiamo con A[x;y] la porzione di A costituita da A[x], A[x+1],…,A[y]
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl5
Merge (A, i1, f1, f2)
1. Sia X un array ausiliario di lunghezza f2-i1+1
2. i=1
3. i2=f1+1
4. while (i1 f1 e i2 f2) do
5. if (A[i1] A[i2])
6. then X[i]=A[i1]
7. incrementa i e i1
8. else X[i]=A[i2]
9. incrementa i e i2
10. if (i1<f1) then copia A[i1;f1] alla fine di X
11. else copia A[i2;f2] alla fine di X
12. copia X in A[i1;f2]
fonde A[i1;f1] e A[f1+1;f2] output in A[i1;f2]
Osservazione: sto usando un array
ausiliario
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl6
LemmaLa procedure Merge fonde due sequenze ordinate di lunghezza n1 e n2 eseguendo al più n1+ n2 -1 confronti
dimOgni confronto “consuma” un elemento di A.Nel caso peggiore tutti gli elementi tranne l’ultimo sonoaggiunti alla sequenza X tramite un confronto.Il numero totale di elementi è n1+ n2. Quindi il numero totaledi confronti è n1+ n2 -1.
numero di confronti nel caso peggiore è (n1+ n2)
Il numero di operazioni (confronti + copie)? (n1+ n2)
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl7
MergeSort (A, i, f)
1. if (i f) then return
2. m = (i+f)/2
3. MergeSort(A,i,m)
4. MergeSort(A,m+1,f)
5. Merge(A,i,m,f)
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl8
• Il numero di confronti del MergeSort è descritto dalla seguente relazione di ricorrenza:
C(n) = 2 C(n/2) + O(n)
• Usando il Teorema Master si ottiene
C(n) = O(n log n)
Tempo di esecuzione
a=b=2, f(n)=O(n) caso 2
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl9
…alcune osservazioni…
• Il MergeSort è un algoritmo (asintoticamente) ottimo rispetto al numero di confronti eseguiti nel caso peggiore
• Il MergeSort non ordina in loco – occupazione di memoria pari a 2n
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl10
• Stesso approccio incrementale del selectionSort– seleziona gli elementi dal più grande al più piccolo– usa una struttura dati efficiente
• estrazione in tempo O(log n) del massimo
• Tipo di dato– Specifica delle operazioni di interesse su una collezione di oggetti (es.
inserisci, cancella, cerca)
• Struttura dati– Organizzazione dei dati che permette di supportare le operazioni di un
tipo di dato usando meno risorse di calcolo possibile
• Cruciale: progettare una struttura dati H su cui eseguire efficientemente le operazioni:– dato un array A, generare velocemente H– trovare il più grande oggetto in H– cancellare il più grande oggetto da H
HeapSort
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl11
Alberi: qualche altra definizione
d=2 albero binario
albero d-ario: albero in cui tutti i nodi interni hanno d figli
un albero d-ario è completo se tutte le foglie sono allo stesso livello
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl12
• Struttura dati heap associata ad un insieme S = albero binario radicato con le seguenti proprietà:1) completo fino al penultimo livello (foglie
sull’ultimo livello tutte compattate a sinistra)
2) gli elementi di S sono memorizzati nei nodi dell’albero
3) chiave(padre(v)) ≥ chiave(v) per ogni nodo v
HeapSort
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl13
16
1014
3978
1 42
In questa direzione è presente un ordinamento
In questa direzione non è presente un ordinamento
…un esempio
il massimo ècontenuto
nella radice!
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl14
Struttura dati heap
37
22 31
14251513
37 912
37 22 31 13 15 25 14 7 3 12 9
vettore posizionale
0 1 2 3 4 5 6 7 8 9 10 11
è sufficiente un vettore di dimensione n
Rappresentazione con vettore posizionale
sin(i) = 2ides(i) = 2i+1padre(i)=i/2
in generale
dimensione vettore
diverso da numero
elementi
nello pseudocodice numero oggettiindicato con heapsize[A]
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl15
Proprietà salienti degli heap
1) Il massimo è contenuto nella radice
2) L’albero ha altezza O(log n)
3) Gli heap con struttura rafforzata possono essere
rappresentati in un array di dimensione pari a n
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl16
fixHeap(nodo v, heap H) if (v è una foglia) then return else sia u il figlio di v con chiave massima if ( chiave(v) < chiave(u) ) then scambia chiave(v) e chiave(u) fixHeap(u,H)
La procedura fixHeap
Se tutti i nodi di H tranne v soddisfano la proprietà di ordinamento a heap, possiamo ripristinarla come segue:
Tempo di esecuzione: O(log n)
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl17
FixHeap - esempio16
104
39714
1 82
i=1
76
32
54
8 9 10
16
1014
3974
1 82
i=1
76
32
54
8 9 10
16
1014
3978
1 42
76
32
54
8 9 10
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl18
fixHeap (i,A)
1. s=sin(i)
2. d=des(i)
3. if (s heapsize[A] e A[s] >A[i])
4. then massimo=s
5. else massimo=i
6. if (d heapsize[A] e A[d] >A[massimo])
7. then massimo=d
8. if (massimoi)
9. then scambia A[i] e A[massimo]
10. fixHeap(massimo,A)
…uno pseudocodice di fixHeap più dettagliato…
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl19
• Copia nella radice la chiave contenuta nella la foglia più a destra dell’ultimo livello– nota: è l’elemento in posizione n (n: dimensione heap)
• Rimuovi la foglia
• Ripristina la proprietà di ordinamento a heap richiamando fixHeap sulla radice
Estrazione del massimo
Tempo di esecuzione: O(log n)
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl20
heapify(heap H) if (H è vuoto) then return else heapify(sottoalbero sinistro di H) heapify(sottoalbero destro di H) fixHeap(radice di H,H)
Costruzione dell’heap
Algoritmo ricorsivo basato sul divide et impera
Tempo di esecuzione: T(n)= 2T(n/2)+O(log n)
T(n) = O(n) dal Teorema Master
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl21
heapify (A)
1. Heapsize[A]=n
2. for i=n/2 down to 1 do
3. fixHeap(i,A)
…una versione iterativa di heapify…
Nota: gli elementi A[n/2+1],…,A[n] sono foglie dell’albero
H
1hnodi
H
1hFixHeapnodi
1 altezza di nodi
FixHeap hOhNhThNTT(n)
H = altezza albero log2(n)Nnodi(h) = numero di nodi di altezza h n/2h+1 ( n/2h+1 )
O(n)nC 2
h
2
nCh
2
nCT(n)
1hh
log(n)
1h1h
2
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl22
• Costruisce un heap tramite heapify
• Estrae ripetutamente il massimo per n-1 volte– ad ogni estrazione memorizza il massimo nella posizione
dell’array che si è appena liberata
L’algoritmo HeapSort
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl23
Esempio di esecuzione
37 31 22 13 15 25
37
31
251513
22
22
15 13
22 15 13 25 31 37
(1)
(4)
31
25
1513
22
31 25 22 13 15 37
15
13
15 13 22 25 31 37
(2)
(5)
25
15
13
22
25 15 22 13 31 37
13
13 15 22 25 31 37
(3)
(6)
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl24
heapSort (A)
1. Heapify(A)
2. for i=n down to 2 do
3. scambia A[1] e A[i]
4. Heapsize[A] = Heapsize[A] -1
5. fixHeap(1,A)
ordina in loco in tempo O(n log n)
O(n)
n-1 estrazioni di costoO(log n)
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl25
• Usa la tecnica del divide et impera:
1 Divide: scegli un elemento x della sequenza (perno) e partiziona la sequenza in elementi ≤ x ed elementi >x
2 Risolvi i due sottoproblemi ricorsivamente
3 Impera: restituisci la concatenazione delle due sottosequenze ordinate
QuickSort
Rispetto al MergeSort, divide complesso ed impera semplice
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl26
QuickSort (A)
1. scegli elemento x in A
2. partiziona A rispetto a x calcolando:
3. A1={y A : y x}
4. A2={y A : y > x}
5. if (|A1| > 1) then QuickSort(A1)
6. if (|A2| > 1) then QuickSort(A2)
7. copia la concatenazione di A1 e A2 in A
non partiziona in loco!
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl27
Partizione in loco
• Scorri l’array “in parallelo” da sinistra verso destra e da destra verso sinistra – da sinistra verso destra, ci si ferma su un elemento
maggiore del perno– da destra verso sinistra, ci si ferma su un elemento
minore del perno
• Scambia gli elementi e riprendi la scansione
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl28
Partizione in loco: un esempio
45 12 21 3 67 43 85 29 24 92 63 3 93
45 12 21 3 3 43 85 29 24 92 63 67 93
45 12 21 3 3 43 2924 92 63 67 9385
45 12 93 3 67 43 85 29 24 92 63 3 21
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl29
Partition (A, i, f )
1. x=A[i]
2. inf =i
3. sup= f + 1
4. while (true) do
5. do (inf=inf + 1) while (A[inf] x)
6. do (sup=sup-1) while (A[sup] > x)
7. if (inf < sup) then scambia A[inf] e A[sup]
8. else break
9. scambia A[i] e A[sup]
10. return sup
Tempo di
esecuzione:
O(n)
partiziona A[i;f]rispetto a A[i]
Proprietà:
In ogni istante, gli elementi A[i],…,A[inf-1] sono del perno,
mentre gli elementi A[sup+1],…,A[f] sono > del perno
mette il perno “al centro”
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl30
QuickSort (A, i, f )
1. if (i f) then return
2. m=Partition(A,i,f)
3. QuickSort(A,i,m-1)
4. QuickSort(A, m +1,f)
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl31
Esempio di esecuzione5 1 276
2 45 7 6
1 4 3
3
1 2 3 4 5 5 6 7
1 2 3 4 6
1 3 4
3
input
output
2 45 3 1 7 6 dopo partition5
3 1
5
2 631 4
5
5
43 5
3
5
5
5
1
6
6
6
5
45
7
7
3
L’albero delle chiamate ricorsive può essere sbilanciato
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl32
• Nel caso peggiore, il perno scelto ad ogni passo è il minimo o il massimo degli elementi nell’array
• Il numero di confronti è pertanto:
C(n)=C(n-1) + O(n)
• Svolgendo per iterazione si ottiene
C(n) = O(n2)
Analisi nel caso peggiore
complessità nel caso migliore?
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl33
Caso migliore: O(n log n), partizionamento sempre bilanciato
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl34
…intuizioni sul caso medio…
• problema: la partizione può essere sbilanciata• la probabilità che ad ogni passo si presenti la
partizione peggiore è molto bassa• per partizioni che non sono “troppo sbilanciate”
l’algoritmo è veloce• domanda: quale è la complessità dell’algoritmo
supponendo che l’algoritmo di partizionamento produca sempre una partizione proporzionale 9-a-1
• Nota: sembra una partizione piuttosto sbilanciata…
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl35
…la complessità è ancora O(n log n)
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl36
Randomizzazione• Possiamo evitare il caso peggiore scegliendo
come perno un elemento a caso
• Poiché ogni elemento ha la stessa probabilità, pari a 1/n, di essere scelto come perno, il numero di confronti nel caso atteso è:
a=0
n-1
C(n)= n-1+C(a)+C(n-a-1)1n
a=0
n-1
= n-1+ C(a)2n
dove a e (n-a-1) sono le dimensioni dei sottoproblemi risolti ricorsivamente
Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati
Copyright © 2004 - The McGraw - Hill Companies, srl37
La relazione di ricorrenza del quicksort ha soluzione
Analisi nel caso medio
C(n) ≤ 2 n log n
Dimostrazione per sostituzione integrando per parti