Universita' di Ferrara
Facolta' di Scienze Matematiche, Fisiche e Naturali
Laurea Specialistica in Informatica
Algoritmi Avanzati
Complessita' degli algoritmi e dei problemi:
sorting e searching
•
•
•
•
straight insertion
ricerca binaria
mergesort, heapsort
radix sort (detto anche distribution sort)
Copyright © 2006-2009 by Claudio Salati.
Lez. 5
1
COMPLESSITA' DEGLI ALGORITMI
Perche' perdere tempo ad analizzare la complessita' di un
algoritmo?
•
Puo' essere divertente.
•
Per mettere alla prova la propria capacita' di preveggenza.
•
Perche' si e' studiosi di efficienza.
•
Per scrivere algoritmi piu' efficienti che ci permettano di
risparmiare tempo e spazio.
(perche' volere risparmiare tempo e spazio? Vedi ad es. S.
Penge, Zen e arte della programmazione)
2
COMPLESSITA' SPAZIALE E TEMPORALE
• Si puo' distinguere tra
• complessita' temporale: occupazione di tempo di CPU per
l'esecuzione di un programma
• complessita' spaziale: occupazione di spazio di memoria
per ospitare le strutture dati utilizzate dal programma.
• Noi ci occuperemo principalmente di complessita' temporale
• La complessita' viene comunque misurata in funzione delle
dimensioni del problema
• Teorema: se la complessita' spaziale e' O(g(n)) allora la
complessita' temporale e' almeno O(g(n)).
(non vale il viceversa)
Dimostrazione: se ho creato delle strutture dati per risolvere il
problema, devo averle scritte e/o lette almeno 1 volta: se le
dimensioni delle strutture dati sono O(g(n)), per fare questo non
3
posso avere impiegato meno di O(g(n)) tempo.
CALCOLO DELLA COMPLESSITA' (temporale)
• Ipotesi di lavoro:
• si esegue una istruzione alla volta
• il costo di un algoritmo dipende dal numero di istruzioni che
richiede di eseguire (non dalla lunghezza del suo testo)
• ogni accesso in memoria ha lo stesso costo
 il metodo piu' accurato per misurare le prestazioni di un algoritmo e'
contare le azioni che sono eseguite durante la sua esecuzione
• per le operazioni elementari si puo' individuare (si assume) un
costo (tempo) fisso/costante
• le operazioni complesse possono essere scomposte in
operazioni elementari
• una analisi a priori del tempo di calcolo ignora tutti i fattori
dipendenti dalla macchina o dal linguaggio di programmazione,
e si concentra sulla determinazione dell'ordine di grandezza
4
della complessita' dell'algoritmo
Complessita' e suo UPPER BOUND
• Definizione: per complessita' di un algoritmo intendiamo la somma
delle frequenze di esecuzione di tutti i suoi statement (in funzione
della dimensione del problema che si sta affrontando)
• Definizione:
• f(n) = O(g(n))
(si legge: f di n uguale O grande di g di n)
se esistono due costanti positive c ed n0 tali che
| f(n) |  c * | g(n) | per tutti gli n  n0
• una analisi a priori del tempo di calcolo f(n) di un algoritmo puo'
essere usata per determinare una funzione g(n) tale che f(n) = O(g(n))
• Con l'algoritmo ha un tempo di calcolo O(g(n)) intendiamo che se
l'algoritmo e' eseguito su un qualche computer, sullo stesso tipo di
dati, per valori crescenti della dimensione n dei dati di ingresso, i
tempi risultanti sono sempre minori di c * | g(n) |, con c costante
positiva.
5
UPPER BOUND
• Teorema: se A(n) = am * nm + … + a1 * n + a0 e' un polinomio di
grado m allora A(n) = O(nm)
• Dimostrazione:
• | A(n) |
 | a m | * nm + … + | a 1 | * n + | a 0 | =
= ( | am | + | am-1 | / n + … + | a0 | / nm ) * nm 
(per n1)
 ( | am | + | am-1 | + … + | a0 | ) * nm
• scegliendo n0 = 1 e c = ( | am | + | am | + … + | a0 | ) si ha
| A(n) |
 c * nm, cioe' A(n) = O(nm)
QED
• Conclusioni:
• se descriviamo la frequenza di esecuzione di uno statement con
un polinomio di grado m come A(n) allora il tempo di calcolo
dello statement e' O(nm)
• tramite la notazione O() esprimiamo una funzione che e' un
upper bound della complessita' dell'algoritmo
6
COMPLESSITA' DEGLI ALGORITMI
Quale e' l'importanza della costante associata all'ordine di
complessita'?
•
Consideriamo due algoritmi che risolvono lo stesso problema, il
primo di complessita' O(n) ed il secondo di complessita' O(n2).
Quale e' il migliore?
•
Se le complessita' effettive sono 10*n e 1*n2 rispettivamente, il
primo algoritmo e' migliore del secondo per tutti gli n>10
•
Se le complessita' effettive sono 104*n e 1*n2 rispettivamente, il
primo algoritmo e' migliore del secondo solo per tutti gli n>104
 La costante associata all'ordine di grandezza mi dice fino a
quali dimensioni un problema puo' essere considerato piccolo e
risolubile (magari convenientemente) con algoritmi banali.
7
COMPLESSITA' ASINTOTICA
Perche' e' importante la complessita' asintotica (cioe' l'ordine di
grandezza della complessita')?
 Perche' e' lei che determina la dimensione massima dei problemi
trattabili con un algoritmo
•
Se le dimensioni dei problemi sono piccole, tutti gli algoritmi
richiedono comunque "poco" tempo e sono "equivalenti"!
•
Consideriamo il valore di alcune funzioni al crescere di n:
•
• f(n) = n :
1
2
3
4
• f(n) = n2 :
1
4
9
16 25 36 49 64 81 100
• f(n) = n3 :
1
8
27 64 125 …
• f(n) = 2n :
2
4
8
5
6
7
8
9
10
1000
16 32 64 128 256 512 1024
Consideriamo in particolare, al crescere di n, il valore della
funzione f(n) = n*log(n):
• f(2)=2
f(3)=4.8 f(4)=8
• f(8)=24 f(9)=28.5
f(5)=11.6
f(10)=33.2
f(6)=15.5
f(100)=664.4
f(7)=19.7
8
COMPLESSITA' ASINTOTICA
• Dati due algoritmi di complessita' asintotica
•
O(n*log(n))
•
O(nx)
e
con x>1,
esiste un valore n0 tale che per tutti i valori n>n0 (problemi di grandi
dimensioni) e' migliore il primo,
mentre per valori bassi di n diventano significativi, al fine del
confronto, il valore di x, il coefficiente del termine di grado massimo
ed i termini di grado minore per cui puo' risultare piu' conveniente il
secondo algoritmo
 Un algoritmo di complessita' asintotica O(n*log(n)) e' "quasi lineare"
 Quindi e' molto buono, perche' e' difficile essere meglio che lineare
(se leggo tutti i dati in ingresso almeno una volta ho gia' una
complessita' almeno lineare!)
9
COMPLESSITA' DEGLI ALGORITMI
•
La dimensione del problema per la quale un algoritmo richiede meno
operazioni di un altro dipende
• dal coefficiente del termine di grado massimo
• dai termini di ordine minore e dai loro coefficienti
•
Questi elementi dipendono:
• dall'algoritmo e dalla sua codifica (e.g. iterazione vs.
ricorsione)
• dal calcolatore che si usa e dal suo set di istruzioni
• dal linguaggio e dal sistema di programmazione utilizzati
•
In una analisi a priori del tempo di calcolo di un algoritmo non
vengono considerati fattori dipendenti dalla codifica, dalla macchina
e dal linguaggio utilizzati;
Si determinano l'ordine di grandezza (l'upper bound), ed
eventualmente quei termini che influenzano significativamente il
confronto, basandosi sulla sola struttura dell'algoritmo
10
LOWER BOUND
• Definizione:
• f(n) = (g(n))
(si legge: f di n uguale omega di g di n)
se esistono due costanti positive c ed n0 tali che
| f(n) |  c * | g(n) | per tutti gli n  n0
• Con l'algoritmo ha un tempo di calcolo (g(n)) intendiamo che se
l'algoritmo e' eseguito su un qualche computer, sullo stesso tipo
di dati, per valori crescenti di dimensione n dei dati di ingresso, i
tempi risultanti sono sempre superiori a c * | g(n) |, con c
costante positiva.
• Tramite la notazione  esprimiamo un lower bound della
complessita' dell'algoritmo
• La nozione di lower bound si puo' pero' applicare non solo alla
complessita' di un algoritmo, ma anche a quella di un problema
11
Complessita' dei Problemi e degli Algoritmi
• Bubblesort e' sia O(n2) che (n2), ma puo' essere (n) se lo si scrive
nella forma:
while (nella iterazione precedente
ci sono stati scambi) {
...
}
• Straight selection e' sia O(n2) che (n2)
• Mergesort e' sia O(n*log(n)) che (n*log(n))
• A noi in genere interessano i lower bound dei problemi, non degli
algoritmi, infatti
 il lower bound di un problema rappresenta l'upper bound
minimo di tutti gli algoritmi (noti e non noti) che lo risolvono
• Se il lower bound di un problema e' (f(n)) cio' vuol dire che non
esiste (non puo' esistere) nessun algoritmo con upper bound minore
12
di O(f(n))
Analisi del caso peggiore e Upper bound
•
Il calcolo della complessita' dell'algoritmo viene effettuato
contando il numero delle istruzioni eseguite, ponendosi in una
situazione che
1. Maggiormente penalizza il tempo di calcolo

analisi del caso peggiore
2. Rende medio il tempo di calcolo

•
analisi del caso medio
Considerare una condizione media comporta in generale
complesse valutazioni probabilistiche, per cui di solito ci si limita
ad analizzare il caso peggiore:
 si cerca cioe' l'upper bound della complessita' di un
algoritmo
13
Complessita' dell'algoritmo di sort per
straight selection
•
Il numero di confronti (all'interno della funzione
findMinEl()) e' indipendente dalla situazione iniziale
(dall'ordine iniziale degli elementi nel vettore)
•
Ad ogni iterazione del ciclo esterno della funzione
straightSelection() devo effettuare 3 assegnamenti
•
Il caso peggiore si ha quando ad ogni iterazione del ciclo della
funzione findMinEl() devo effettuare 1 assegnamento
(cio' avviene quando il vettore e' inizialmente ordinato in modo
non crescente)
•
il ciclo esterno e' ripetuto n-1 volte
•
nel caso peggiore l'i-esima iterazione prevede (trascurando le
operazioni di controllo del ciclo)
• 3 + (n-i-1) assegnamenti
• (n-i-1) confronti
per un totale di operazioni di … (lasciato per esercizio)
•
e quindi una complessita' O(n )
2
14
Sort di un vettore: Straight insertion
• Problema: Dato un vettore di N elementi interi, N1, ordinarlo in
modo non decrescente
• Fino ad ora abbiamo visto 2 algoritmi, basati su due diverse
strategie, ma in ogni caso di complessita' quadratica:
• straight selection
• straight exchange o bubblesort
• Vediamo una terza strategia: Straight insertion
• ALL’i-ESIMA ITERAZIONE IL SOTTOVETTORE v[0..i-1] E’ GIA’
ORDINATO (ma solo al proprio interno, non rispetto al resto di v)
• SI PRENDE L’ELEMENTO DI INDICE i E LO SI INSERISCE
NELLA POSIZIONE APPROPRIATA ALL’INTERNO DEL
SOTTOVETTORE GIA’ ORDINATO, TRASLANDO IN AVANTI
DI UN POSTO NEL VETTORE GLI ELEMENTI CHE SONO
MAGGIORI DI LUI
• C'E' SPAZIO PER FARLO PERCHE' DAL VETTORE E' STATO
15
ESTRATTO L'ELEMENTO DI INDICE i
Straight Insertion: la strategia
•
Situazione all'i-esima iterazione del ciclo:
vettore v
v[0] .. v[i-1] ordinato
v[i]
v[i+1]
...
v[N-1]
i
v[0]..v[i-1] tratto del vettore gia' internamente ordinato in
modo non decrescente.
Questo sottovettore deriva dal processamento
sequenziale degli i precedenti elementi del vettore
originale.
Non c'e' relazione tra gli elementi del sottovettore
v[0]..v[i-1] e quelli del sottovettore v[i]..v[N-1]
i
indice dell'elemento del vettore che si vuole
inserire al posto giusto nel sottovettore ordinato
v[0]..v[i-1]
16
Straight Insertion: l'algoritmo
void straightInsertion(int n, int v[]) {
1
int i = 1;
// { P; in; (j: 0<ji-1) v[j-1]v[j] }
while (i <= n-1) {
int toInsert =
whereToInsert(0, i-1, v, v[i]);
// { in-1; (j: 0jtoInsert-1) v[j]v[i];
//
(j: toInsertji-1) v[j]>v[i]; }
int temp = v[i];
shiftOneRight(toInsert, i-1, v);
v[toInsert] = temp;
i += 1;
// { in; (j: 0<ji-1) v[j-1]v[j] }
}
// { i=n; (j: 0<jn-1) v[j-1]v[j] }
2
3
4
5
6
7
8
9
}
10
17
Straight Insertion: l'algoritmo
int whereToInsert(int low, int high,
int v[], int el) {
1
// 0lowhigh<size | int v[size]
// (j: low<jhigh) v[j-1]v[j]
int scan = low;
// (j: low<jhigh) v[j-1]v[j]
// (j: lowjscan-1) v[j]el
// scan  high+1
while (scan <= high && v[scan] <= el) scan +=1;
// (j: low<jhigh) v[j-1]v[j]
// (j: lowjscan-1) v[j]el
// (j: scanjhigh) v[j]>el
// scan  high+1
return scan;
2
3
4
}
5
18
Straight Insertion: l'algoritmo
void shiftOneRight(int low, int high, int v[]) {
1
// 0<=low, low-1 <= high,
// 0<=high<size-1 | int v[size]
int scan = high;
while (scan >= low) {
v[scan+1] = v[scan];
scan -= 1;
}
}
2
3
4
5
6
7
19
Straight Insertion:
correttezza, terminazione, complessita'
• Correttezza:
lasciata per esercizio
• Terminazione:
lasciata per esercizio
• Complessita':
• ad ogni iterazione del ciclo esterno vengono effettuati
• toInsert confronti per localizzare la posizione in v
(nel sottovettore v[0]..v[i-1]) in cui inserire v[i]
• ed i-toInsert assegnamenti per spostare di una
posizione a destra gli elementi del sottovettore
v[toInsert]..v[i]
• per cui anche questo algoritmo e' quadratico
20
RICERCA BINARIA
• Ma e' veramente necessario impiegare O(i) confronti per
localizzare la posizione in v[] (in particolare nel sottovettore
v[0]..v[i-1]) in cui inserire v[i]
• Il sottovettore v[0]..v[i-1]e' internamente ordinato!
• Confrontiamo v[i] con v[i/2]
• se v[i]=v[i/2] possiamo inserire v[i] in posizione
i/2 (o i/2+1: va bene lo stesso)
• se v[i]<v[i/2] sicuramente non dovremo inserire v[i]
a destra di v[i/2]
• per localizzare la posizione in cui inserire v[i] a sinistra
di v[i/2] possiamo applicare ricorsivamente la stessa
strategia, confrontando v[i] con v[(i/2)/2]
• possiamo ovviamente procedere in modo analogo e
speculare nel caso v[i]>v[i/2]
21
RICERCA BINARIA: l'algoritmo (del dizionario)
int whereToInsert(int low, int high,
int v[], int el) {
//
//
//
//
0lowhigh<size | int v[size]
(j: 0<jsize-1) v[j-1]v[j]
(j: 0jlow-1) v[j]el
(j: high+1jsize) v[j]>el
. . .
// low  return  high+1
// (j: 0<jsize-1) v[j-1]v[j]
// (j: lowjreturn-1) v[j]el
// (j: returnjhigh) v[j]>el
}
22
RICERCA BINARIA: la strategia
•
Situazione all'i-esima chiamata ricorsiva:
vettore v
...
v[low]
low
v[low..high]
...
v[high]
high
...
v[size]
size
tratto del vettore sotto esame. Gli elementi di
questo sottovettore sono tra loro ordinati.
v[0..low-1]
tratti del vettore non significativi. Si assume che
v[high+1..size] gli elementi contenuti in questi sotto-vettori, veri o
fittizi, siano comunque ordinati e che
• tutti gli elementi del primo sottovettore siano
el
• tutti gli elementi del secondo sottovettore
siano >el
23
RICERCA BINARIA: la strategia
•
N.B.: si assume per comodita' che tutti gli elementi del vettore,
anche quelli esterni al range di interesse, siano ordinati e di
valore opportuno (vedi pagina precedente).
•
Si assume anche che il vettore si prolunghi con un elemento
fittizio di indice size (essendo size la dimensione del vettore).
Ovviamente v[size] e' assunto >el.
•
Ovviamente non ha senso accedere gli elementi esterni al range
di interesse low..high, sia che siano veri, sia che siano fittizi.
(e' comunque impossibile sapere a priori se sono veri o fittizi,
eccetto v[size] che e' fittizio)
24
RICERCA BINARIA: l'algoritmo
int whereToInsert(int low, int high,
int v[], int el) {
int scan = (low + high) / 2;
if (v[scan] <= el) {
int newLow = scan + 1;
if (newLow <= high)
return whereToInsert(newLow, high, v, el);
else
return newLow;
// end if
} else { // v[scan]>el
int newHigh = scan;
if (newHigh > low)
return whereToInsert(low, newHigh-1, v, el);
else
return newHigh;
// end if
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2516
RICERCA BINARIA: analisi dell'algoritmo 1
int whereToInsert(int low, int high,
int v[], int el) {
// (j: 0jlow-1) v[j]el
// (j: high+1jsize) v[j]>el
int scan = (low + high) / 2;
// lowscanhigh
if (v[scan] <= el) {
// (j: 0jscan) v[j]el
// (j: high+1jsize) v[j]>el
int newLow = scan + 1; // newLow  high+1
// (j: 0jnewLow-1) v[j]el
// (j: high+1jsize) v[j]>el
if (newLow <= high)
return whereToInsert(newLow, high, v, el);
else // newLow = high+1, era low=high
// (j: 0jnewLow-1) v[j]el
// (j: newLowjsize) v[j]>el
return newLow;
// end if
26
} else {...
RICERCA BINARIA: analisi dell'algoritmo 2
int whereToInsert(int low, int high,
int v[], int el) {
// (j: 0jlow-1) v[j]el
// (j: high+1jsize) v[j]>el
int scan = (low + high) / 2;
// lowscanhigh
if (v[scan] <= el) { ...
} else { // v[scan]>el
int newHigh = scan;
// (j: 0jlow-1) v[j]el
// (j: newHighjsize) v[j]>el
if (newHigh > low)
return whereToInsert(low, newHigh-1, v, el);
else // newHigh=low
// (j: 0jnewHigh-1) v[j]el
// (j: newHighjsize) v[j]>el
return newHigh;
// end if
}
27
}
Ricerca binaria:
correttezza, terminazione, complessita'
• Correttezza:
la dimostrazione e' per induzione sulla lunghezza del
sottovettore da esaminare, cioe' sulla differenza high-low
base dell'induzione: se low=high allora anche
scan=high=low.
• Se v[scan]el allora newLow>high e la funzione
ritorna correttamente high+1
• Se v[scan]>el allora newHigh=low e la funzione
ritorna correttamente low
(devo inserire el in posizione low, traslando in avanti
v[low])
passo induttivo: vedi lucido successivo.
28
Ricerca binaria:
correttezza, terminazione, complessita'
• Correttezza (continua):
passo induttivo: supponiamo che l'algoritmo funzioni kn, e
dimostriamo che funziona per n+1:
(quindi possiamo assumere high>low)
In questo caso lowscan<high.
• Se v[scan]el allora low<newLowhigh e
high-newLow<n, per cui la funzione si comporta
correttamente per ipotesi induttiva (ipotesi induttiva applicabile,
precondizioni della funzione soddisfatte)
• Se v[scan]>el allora
• se newHigh=low la funzione ritorna correttamente low
• se newHigh>low allora newHigh-1-low<n, per cui la
funzione si comporta correttamente per ipotesi induttiva 29
Straight Insertion: verso Mergesort
• Ordine di complessita' della funzione di ricerca binaria: O(log(n))
infatti ad ogni confronto si dimezza la dimensione del vettore da
esaminare
• La complessita' asintotica di Straight Insertion migliora avendo
ridotto da lineare a logaritmica la complessita' di
whereToInsert()?
• No, perche' rimane comunque lineare la complessita' di
shiftOneRight()
• Supponiamo pero' di utilizzare una tecnica simile a quella della
ricerca binaria a Straight Insertion nel suo complesso:
• nella ricerca binaria ad ogni ricorsione dimezzo la
dimensione del sottovettore che devo esaminare, e riconduco
la soluzione del problema dimensione n a quella del
problema di dimensione n/2.
• applichiamo la stessa tecnica a Straight Insertion.
30
Straight Insertion: verso Mergesort
• Divido il problema di ordinare un vettore di dimensione n in quello di
ordinare due sottovettori di dimensione n/2
• Risolto questo, inserisco in modo ordinato gli elementi del secondo
sottovettore nel primo sottovettore.
• Perche' dovrebbe essere piu' efficiente che nel caso di Straight
Insertion?
• Dimezzando la dimensione di un problema quadratico, la sua
soluzione e' 4 volte piu' facile!
• L'inserimento puo' tenere conto del fatto che gli elementi del
secondo sottovettore sono anch'essi ordinati
(mentre nel caso di Straight Insertion l'inserimento avviene a
partire da un secondo sottovettore non ordinato):
 una volta inserito il primo elemento, il secondo dovra' essere
inserito nel sottovettore ordinato alla sua destra!
• Ovviamente dovro' evitare operazioni di traslazione!
31
MERGESORT: la strategia
• Problema:
Dato un vettore di N elementi interi, N1, ordinarlo in modo non
decrescente
• Premessa:
P = { N1, int v[N] }
• Conseguenza:
C = { N1, int v[N], j=0..N-2 : v[j]  v[j+1] }
• Strategia:
1. si opera in modo ricorsivo;
2. si divide il vettore in due sottovettori:
il sottovettore v[0]..v[(N-1)/2] e il sottovettore v[(N-1)/2+1]..v[N-1];
3. si ordina in modo indipendente ciascuno dei due sottovettori;
4. si fa il merge (fusione) ordinato dei due sottovettori ordinati
in un unico vettore globalmente ordinato.
32
Mergesort: perche' questa strategia?
• Perche' questa strategia?
•
Perche' gli algoritmi di sort considerati fino ad ora sono tutti di
complessita' O(n2).
•
Quindi, se divido per 2 la dimensione del problema la sua
soluzione diventa 4 volte piu' rapida!
•
E risolvere entrambi i sottoproblemi mi costa (al piu') solo la
meta' che risolvere il problema originale.
(utilizzando uno degli algoritmi quadratici gia' noti)
•
Mi resta ancora meta' del tempo per operare la fusione delle
due soluzioni parziali: se la fusione e' facile, globalmente ci
guadagno.
•
In realta', ovviamente, anche i due sottoproblemi possono
essere risolti utilizzando ricorsivamente la stessa strategia.
33
Mergesort: l'algoritmo
void mergeSort(int v[],
int low, int high) {
assert(low<=high);
if (low<high) {
int middle = (low + high) / 2;
// low<=middle<high
mergeSort(v, low, middle);
// (j: low<jmiddle) v[j-1]v[j]
mergeSort(v, middle+1, high);
// (j: low<jmiddle) v[j-1]v[j]
// (j: middle+1<jhigh) v[j-1]v[j]
merge(v, low, middle, high);
// (j: low<jhigh) v[j-1]v[j]
}
}
1
2
3
4
5
7
8
9
34
Mergesort: l'algoritmo di merge - 1
void merge(int v[],
int low, int middle, int high) {
int *pBufferV = malloc((high-low+1) *
sizeof(int));
int bufferIndex = 0;
int lowScan = low;
int highScan = middle + 1;
while (lowScan<=middle && highScan<=high) {
if (v[lowScan]<=v[highScan]) {
pBufferV[bufferIndex] = v[lowScan];
lowScan += 1;
} else {
pBufferV[bufferIndex] = v[highScan];
highScan += 1;
}
bufferIndex += 1;
}
// continua alla pagina seguente
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
35
Mergesort: l'algoritmo di merge - 2
if (lowScan>middle) // && highScan<=high
while (highScan<=high) {
pBufferV[bufferIndex] = v[highScan];
highScan += 1;
bufferIndex += 1;
}
else // lowScan<=middle && highScan>high
while (lowScan<=middle) {
pBufferV[bufferIndex] = v[lowScan];
lowScan += 1;
bufferIndex += 1;
}
// end if
// continua alla pagina seguente
17
18
19
20
21
22
23
24
25
26
27
28
36
Mergesort: l'algoritmo di merge - 3
for (bufferIndex = 0, lowScan = low;
lowScan<=high;
bufferIndex += 1, lowScan +=1)
v[lowScan] = pBufferV[bufferIndex];
// end for
free(pBufferV);
// punto 1:
//
//
//
//
//
29
30
31
32
33
avete notato che quando si alloca memoria
bisogna indicare di quanta se ne ha bisogno,
ma quando si libera memoria non occorre
indicare quanta se ne libera!
Strano! o no?
// punto 2:
//
//
//
//
//
}
perche' abbiamo utilizzato memoria dinamica
e non memoria automatica, anche se la
disciplina di allocazione che abbiamo
realizzato e' identica a quella che e' usata
per la memoria automatica?
34
37
Mergesort: esercizi
1. Aggiungere a merge() tutte le asserzioni ritenute significative
per ottenere una buona documentazione della funzione.
Considerare in particolare
•
precondizioni
•
postcondizioni (prima della copiatura finale all’indietro,
cioe' prima della riga 29)
•
invariante del primo ciclo
2. Perche' nella realizzazione di merge() non ci si e' accontentati
di allocare come variabile automatica un vettore di dimensione
costante (fissata a tempo di compilazione)?
Considerare
•
problemi di efficienza
•
problemi di funzionalita'
38
Mergesort: risposte parziali
Invariante del primo ciclo (riga 7) di merge()
•
lowScan  middle  highScan  high
(N.B. cio', insieme alla negazione della condizione di controllo del ciclo,
garantisce che esattamente uno dei due rami dell'if successivo, riga
17, sia eseguito)
•
bufferIndex-0 = (lowScan-low + highScan-(middle+1))
•
j=0..bufferIndex-2 : pBufferV[j]  pBufferV[j+1]
•
j=low..middle-1 : v[j]  v[j+1]
•
j=middle+1..high-1 : v[j]  v[j+1]
•
(j=lowScan..middle, k= 0..bufferIndex) : v[j]  pBufferV[k]
•
(j=highScan..high, k= 0..bufferIndex) : v[j]  pBufferV[k]
•
j=low..lowScan-1 : v[j]  pBufferV[0.. bufferIndex-1]
•
j=middle+1..highScan-1 : v[j]  pBufferV[0.. bufferIndex-1]
39
Mergesort: correttezza
•
MERGESORT E' CORRETTA:
• ASSUMIAMO LA CORRETTEZZA DELL'ALGORITMO DI MERGE.
• LA CORRETTEZZA DI MERGESORT SI STABILISCE PER
INDUZIONEMATEMATICA SUL NUMERO DEGLI ELEMENTI DEL
VETTORE.
• BASE: SE LUNGO 1 (low=high) E' GIA' ORDINATO E NON SI FA
NIENTE
• INDUZIONE: SE PIU' LUNGO, CIASCUNA DELLE DUE META' E'
ORDINATA PER HP INDUTTIVA, MERGE LAVORA BENE, PER CUI
TUTTO LAVORA BENE
•
MERGE E' CORRETTA:
• TUTTI GLI ELEMENTI DI CIASCUNO DEI SOTTOVETTORI SONO
INSERITI NEL VETTORE FINALE: QUELLI NON INSERITI NEL PRIMO
LOOP LO SONO NEL SECONDO.
• GLI ELEMENTI SONO INSERITI IN ORDINE NON DECRESCENTE
• PERCHE' LO ERANO GIA', E QUINDI PER INDUZIONE SULLA
LUNGHEZZA DEL VETTORE RISULTANTE, NEL PRIMO CICLO
• PERCHE' LO ERANO GIA' NEL SECONDO
40
Mergesort: terminazione
• TERMINAZIONE:
• MERGESORT TERMINA PERCHE' LE RICORSIONI TERMINANO
APPLICANDOSI SEMPRE SU VETTORI DI LUNGHEZZA
DIMEZZATA, PER CUI ALLA FINE SI OTTIENE SEMPRE UN
VETTORE DI LUNGHEZZA 1
(SE high==low+1 ALLORA (low+high)/2==low E middle+1==high)
•
MERGE TERMINA PERCHE':
• A OGNI ITERAZIONE DEL PRIMO LOOP VIENE
INCREMENTATO DI 1 L'INDICE DI SCANSIONE O DELL'UNO
O DELL'ALTRO SOTTOVETTORE
• IL SECONDO LOOP SI APPLICA SOLO SUL VETTORE (CHE
C'E') NON COMPLETAMENTE SCANDITO DAL PRIMO LOOP:
IL LOOP TERMINA PERCHE' L'INDICE DI SCANSIONE DEL
VETTORE E' INCREMENTATO DI 1 AD OGNI ITERAZIONE
• ANCHE L'ULTIMO LOOP TERMINA PER LO STESSO MOTIVO
41
Mergesort: complessita'
• Complessita' dell'algoritmo di merge:
• Ogni iterazione del primo statement while comporta 3 confronti e
3 assegnamenti
• una iterazione del ciclo while contenuto in ciascuno dei rami
dello statement if successivo comporta 1 confronto e 3
assegnamenti
• il totale complessivo delle iterazioni dei due primi cicli while e'
high-low+1
• l'ultimo ciclo (di ricopiatura) e' eseguito' high-low+1 volte, e
comporta 3 assegnamenti e 1 confronto ad ogni iterazione
• quindi l'esecuzione dell funzione merge() comporta
l'esecuzione di meno di 2*(3+3)*(high-low+1)
operazioni
• pertanto la funzione merge() ha complessita' O(n), essendo
evidentemente n= high-low+1 la dimensione del problema 42
Mergesort: complessita'
• Complessita' dell'algoritmo di mergesort:
• la figura seguente mostra la sequenza delle chiamate ricorsive
fatte dalla funzione mergeSort() quando e' applicata ad un
vettore di 10 elementi (di indice da 0 a 9)
• la coppia di valori in ogni nodo rappresenta i valori dei parametri
low e high per quell'attivazione di mergeSort()
• viene anche indicato l'ordine delle operazioni di call e return
• l'operazione di divide continua fino a che ogni nodo contiene un
solo elemento
43
Mergesort: complessita'
• Complessita' dell'algoritmo di mergesort:
Call, return
0, 9
1, 9
10, 18
0, 4
2, 5
5, 9
7, 8
0, 2
11, 14
3, 4
5, 7
3, 3
6, 4
8, 6
9, 7
12, 12
0, 1
2, 2
3, 3
4, 4
5, 6
4, 1
0, 0
5, 2
1, 1
16, 17
13, 10
5, 5
8, 9
15, 13 17, 15
7, 7
8, 8
18, 16
9, 9
14, 11
6, 6
44
Mergesort: complessita'
• Complessita' dell'algoritmo di mergesort:
• la complessita' della funzione mergeSort() e' descritta dalla
seguente relazione ricorsiva:
T(n) =
{
a
con a costante, se n=1
2 * T(n/2) + c * n + c'
con c e c' costanti, se n>1
• espandendo in modo ricorsivo T(n/2) e trascurando la costante
c':
T(n) = 2 * T(n/2) + c * n = 2 * (2 * T(n/4) + c * n/2) + c * n =
= 4 * T(n/4) + 2 * c * n =
= 4 * (2 * T(n/8) + c * n/4) + 2 * c * n =
= 8 * T(n/8) + 3 * c * n =
p
in generale
p
= 2 * T(n/2 ) + p * c * n
45
Parentesi - Esercizio
• verificare, utilizzando il principio di induzione matematica, la
uguaglianza delle due seguenti relazione ricorsive:
1. T(n) = 2 * T(n/2) + c * n
p
p
2. T(n) = 2 * T(n/2 ) + p * c * n
• suggerimento: basta assumere l'uguaglianza per p=n e
verificare che applicando la definizione 1 si ottiene la relazione 2
per p=n+1
46
Mergesort: complessita'
• Complessita' dell'algoritmo di mergesort:
•
T(n) = 2p * T(n/2p) + p * c * n
• dove
p
p
• 2 * T(n/2 ) e' il costo dell'attivazione ricorsiva di
mergeSort()
• p * c * n e' il costo delle attivazioni della funzione merge()
• ponendo p = log2n
p
(e quindi 2 =n)
T(n) = n * T(1) + log2n * c * n = a * n + c * n * log2n
e quindi
T(n) = O(n * log2n) = O(n * log(n))
47
Mergesort: complessita'
• Perche’ la strategia adottata per mergesort funzioni occorre che
la suddivisione del vettore avvenga in due sotto-vettori bilanciati,
cioe’ di uguale numero di elementi.
• Supponiamo infatti di suddividere il vettore in 2 sotto-vettori, il
primo di n-1 elementi e il secondo di 1 elemento:
• La soluzione del primo problema avrebbe costo
O((n-1)2) = O(n2)
• Quindi no si sarebbe guadagnato niente!
• In effetti, se modifichiamo mergesort suddividendo il vettore in 2
sotto-vettori, il primo di n-1 elementi e il secondo di 1 elemento,
quello che otteniamo e’ la versione ricorsiva di straight-insertion!
48
Complessita' di mergesort e straight selection
• Si e' visto che, considerando il termine di ordine maggiore, le
complessita' di mergesort e straight selection sono rispettivamente
• Tmergesort(n) = c1 * n * log2n
• Tstraightselection (n) = c2 * n2
• da cio' deriva che straight selection e' migliore di mergesort quando
c2 * n2 < c1 * n * log2n
cioe' quando c1 > c2 * n / log2n
• quando il vettore da ordinare e' abbastanza corto puo' essere piu'
conveniente utilizzare straight selection (l'algoritmo asintoticamente
peggiore!)
• N.B.: in realta' quando si calcola la complessita' di un algoritmo di
ordinamento per confronti, normalmente si contano solo i confronti
tra elementi del vettore
49
ORDINAMENTO PER CONFRONTI
COMPLESSITA' DEL PROBLEMA
•
QUANTI SONO I POSSIBILI ORDINAMENTI DI UN INSIEME DI n
ELEMENTI?

n! = n * (n-1) * (n-2) * ... * 1
•
ORDINARE UN INSIEME DI n ELEMENTI SIGNIFICA SELEZIONARE
TRA LE n! PERMUTAZIONI DEGLI ELEMENTI DELL'INSIEME
QUELLA CHE SODDISFA LA RELAZIONE DI ORDINAMENTO
•
LA SELEZIONE AVVIENE PER CONFRONTI DI 2 ELEMENTI, IL CHE
MI PORTA A PRENDERE UNA DECISIONE
•
POSSIAMO QUINDI IMMAGINARE LE n! PERMUTAZIONI COME LE
FOGLIE DI UN ALBERO BINARIO DI DECISIONI CHE CI PERMETTE
DI SELEZIONARE LA PERMUTAZIONE GIUSTA
•
UN ALBERO BINARIO COMPLETO DI ALTEZZA h HA 2h FOGLIE
(ELEMENTARE PER INDUZIONE, E LO VEDREMO DURANTE IL
CORSO) PERCIO' SE LE FOGLIE SONO n!, L'ALTEZZA MINIMA
DELL'ALBERO BINARIO DI DECISIONE E'

log(n!)
50
ORDINAMENTO PER CONFRONTI
COMPLESSITA' DEL PROBLEMA
• UNA APPROSSIMAZIONE DI n! E' (n/e)n E QUINDI
log(n!)
= n * (log(n) - log(e))
= n*log(n) - 1.44*n
= (n*log(n))
• SEGUENDO L'ALBERO DI DECISIONE SI DEBBONO
OPERARE TANTI CONFRONTI QUANTA E' L'ALTEZZA
DELL'ALBERO
• PERTANTO LA COMPLESSITA' DEL PROBLEMA DI
ORDINARE UN VETTORE PER CONFRONTO DI ELEMENTI
E' DI ORDINE n*log(n)
• NON PUO' ESISTERE NESSUN ALGORITMO CHE OPERA
PER CONFRONTO CHE SIA MEGLIO DI O(n*log(n))
• PERTANTO MERGESORT (IN QUESTO SENSO) E' OTTIMO
51
ORDINAMENTO PER CONFRONTI
COMPLESSITA' DEL PROBLEMA
•
SI PUO' FARE DI MEGLIO, OPERANDO PER CONFRONTI?
•
NOTA CHE L'OPERAZIONE DI merge RICHIEDE L'UTILIZZO DI UN
VETTORE DI APPOGGIO IN CUI OPERARE IL MERGE, E QUINDI UNA
COPIATURA ALL'INDIETRO:

LAVORO

SPAZIO: MERGESORT NON OPERA 'SUL POSTO' COME FANNO
GLI ALGORITMI O(n2) VISTI (E.G. BUBBLESORT) MA RICHIEDE
UNO SPAZIO DI MEMORIA AGGIUNTIVO DI DIMENSIONE n
•
LA COMPLESSITA' SPAZIALE DI MERGESORT E' MAGGIORE DI
QUELLA DI BUBBLESORT: 2*n ANZICHE' n
•
IN PIU' C'E' L'OVERHEAD (anche spaziale) DELLE CHIAMATE DI
PROCEDURA E QUELLO DELLA DOPPIA COPIATURA PER IL
MERGING
• Esistono algoritmi di ordinamento per confronto di complessita’
O(n*log(n)) che operano sul posto?

Si', heapsort
52
HEAPSORT
(TREESORT)
• Modificando straight -insertion, che e' di complessita' O(n2),
abbiamo ottenuto un nuovo algoritmo, mergesort, di
complessita' O(n*log(n))
• Un primo tentativo per ottenere questo risultato e' stato quello di
rendere logaritmico, anziche' lineare, il costo di localizzare la
posizione dove inserire il nuovo elemento nel sottovettore gia'
ordinato.
• Ri-consideriamo straight -selection:
 cosa e' che lo rende quadratico?
• Il fatto che ad ogni iterazione il costo per identificare il nuovo
elemento minimo e' lineare:
 sarebbe possibile renderlo logaritmico?
53
HEAPSORT
(TREESORT)
•
NEL PRIMO CICLO DI STRAIGHT SELECTION TRAMITE n-1
CONFRONTI VIENE IDENTIFICATO L'ELEMENTO MINIMO DEL
VETTORE
•
NON SI RACCOGLIE NESSUNA ALTRA INFORMAZIONE RIGUARDO
AGLI ALTRI n-1 ELEMENTI NON MINIMI!
•
COSA POTREMMO FARE IN ALTERNATIVA CON n-1 CONFRONTI A
NOSTRA DISPOSIZIONE?
1. DIVIDIAMO GLI n ELEMENTI IN COPPIE
2. CON n/2 CONFRONTI SI PUO' STABILIRE L'ELEMENTO MINIMO
DI OGNI COPPIA, OTTENENDO n/2 ELEMENTI
3. I PASSI (1) E (2) POSSONO ESSERE ITERATI FINO AD
OTTENERE L'ELEMENTO MINIMO DEL VETTORE, PIU' UN
ALBERO DI RELAZIONI TRA GLI ELEMENTI DEL VETTORE VIA
VIA SELEZIONATI
IL TUTTO CON
•
n/2 + n/4 + n/8 + ... = n-1 CONFRONTI
L'ALBERO COSI' COSTRUITO HA OVVIAMENTE ALTEZZA log(n)
54
HEAPSORT: esempio
•
vettore = [ 44, 55, 12, 42, 94, 18, 6, 67 ]
6
12
6
44
44
12
55
12
18
42
94
6
18
6
67
55
HEAPSORT
•
PROCEDIAMO COME IN STRAIGHT SELECTION:
1. ESTRAIAMO DALL'ALBERO L'ELEMENTO MINIMO.
PER FARLO OCCORRE CANCELLARLO A TUTTI I LIVELLI DELL'ALBERO
SOSTITUENDOLO CON UNA CHIAVE "INDEFINITO".
CIO' IMPLICA log(n) OPERAZIONI.
2. SEGUENDO IL PATH DELL'EX ELEMENTO MINIMO RIEMPIAMO I BUCHI
LASCIATI DALLA SUA CANCELLAZIONE FACENDO EMERGERE DAL
BASSO IL RELATIVO SOSTITUTO.
QUESTA OPERAZIONE COSTA ANCH'ESSA log(n), ED IN PARTICOLARE
IMPLICA log(n) CONFRONTI.
3. SI E' COSI' SELEZIONATO IL SECONDO ELEMENTO MINIMO MA QUESTA
VOLTA IN TEMPO log(n).
4. RIPETENDO I PASSI (1)...(3) FINO A CHE SONO ESTRATTI TUTTI GLI
ELEMENTI DEL VETTORE ORIGINARIO ABBIAMO ORDINATO IL VETTORE
CON UN NUMERO DI CONFRONTI PARI A:
 (n-1) + (n-1)*log(n)
ED IN GENERALE CON UN COSTO
•
O(n*log(n))
LA COSA NON VIENE GRATIS:
• BISOGNA MEMORIZZARE E MANTENERE LA STRUTTURA AD ALBERO.
• OCCORRE TRATTARE LA CHIAVE "INDEFINITO", CHE OLTRE TUTTO
CAUSA CONFRONTI INUTILI.
56
HEAPSORT: esempio
•
vettore = [ 44, 55, 12, 42, 94, 18, 6, 67 ]
6
12
6
44
44
•
12
55
12
18
42
94
6
18
6
67
vettore ordinato = [ ]
57
HEAPSORT: esempio
•
vettore = [ 44, 55, 12, 42, 94, 18, 6, 67 ]
12
44
44
•
12
55
12
18
42
94
18
67
vettore ordinato = [ 6 ]
58
HEAPSORT: esempio
•
vettore = [ 44, 55, 12, 42, 94, 18, 6, 67 ]
12
12
18
44
44
•
12
55
12
18
42
94
67
18
67
vettore ordinato = [ 6 ]
59
HEAPSORT: esempio
•
vettore = [ 44, 55, 12, 42, 94, 18, 6, 67 ]
12
12
18
44
44
•
12
55
12
18
42
94
67
18
67
vettore ordinato = [ 6 ]
60
HEAPSORT: esempio
•
vettore = [ 44, 55, 12, 42, 94, 18, 6, 67 ]
18
44
44
•
18
55
42
94
67
18
67
vettore ordinato = [ 6, 12 ]
61
HEAPSORT: esempio
•
vettore = [ 44, 55, 12, 42, 94, 18, 6, 67 ]
18
42
44
44
•
18
42
55
18
42
94
67
18
67
vettore ordinato = [ 6, 12 ]
62
HEAP
• Ma per mantenere questa organizzazione degli elementi del
vettore che ne riflette degli ordinamenti parziali e' necessario
mantenere, oltre al vettore originario, anche una esplicita struttura
dati ad albero?
• E come fare a costruire questa struttura ad albero?
• L'algoritmo del torneo per identificare l'elemento minimo di un
vettore in linea di principio raccoglie esattamente questa
informazione, ma non la traduce in una struttura dati esplicita.
• In sostanza, sarebbe facile costruire e mantenere la struttura dati
che mi rende espliciti tutti i risultati di tutti gli scontri del torneo?
• Esistono alternative piu' semplici?
• Si' esiste una struttura dati che mi rappresenta sostanzialmente la
stessa informazione dei risultati degli incontri del torneo:
 questa struttura dati e' chiamata heap.
63
HEAP
• il vettore stesso puo' essere strutturato internamente in modo da
mantenere questa informazione:
 Il vettore stesso puo' essere utilizzato per rappresentare un
albero binario.
 In questo albero binario ogni nodo e' minore o uguale dei suoi
figli (se ne ha).
 Un vettore cosi' strutturato e' chiamato heap
• infatti: UN ALBERO BINARIO COMPLETO di n elementi PUO'
ESSERE RAPPRESENTATO IN UN ARRAY (di indici da 0 a n-1)
DOVE I FIGLI SINISTRO E DESTRO DEL NODO i SI TROVANO
RISPETTIVAMENTE AGLI INDICI 2*i+1 E 2*i+2
 perche' i nostri vettori sono indiciati a partire da 0
 se i nostri vettori fossero indiciati a partire da 1 i figli si
troverebbero agli indici i*2 e i*2+1
64
HEAP
• N.B.: un array rappresenta sempre un albero binario completo o quasi
completo
 cioe' un albero che ha tutti i nodi a tutte le profondita' salvo
eventualmente a quella massima, in cui possono essere assenti le
foglie piu’ a destra
• Perche’ un array che rappresenta un albero binario sia uno heap deve
anche valere la regola
• h[i]  h[2*i+1]
• h[i]  h[2*i+2] (se questo elemento esiste)
per ogni i  0 .. (n/2)-1,
cioe' per tutti gli elementi che hanno almeno un figlio (n e' la
dimensione del vettore, i cui indici vanno da 0 a n-1)
• N.B. (n/2)-1 = ((n-1)-1)/2
Poiche' i figli del nodo i si trovano agli indici 2*i+1 e 2*i+2, il padre del
nodo di indice k si trova all'indice (k-1)/2
65
• Nota che, se l’array h e’ uno heap, h[0] e’ l’elemento minimo dell’array
HEAP: esempio
• vettore = [ 4, 12, 6, 14, 22, 18, 16, 44, 55, 23, 42, 94, 19, 26, 67 ]
v[0]=4
v[1]=12
v[3]=14
v[7]
=44
v[2]=6
v[4]=22
v[8]
=55
v[9]
=23
v[10]
=42
v[5]=18
v[11]
=94
• i | 0in/2-1 : v[i]v[2*i+1]  v[i]v[2*i+2]
• i | 0in-1 : v[0]v[i]
v[12]
=19
v[6]=16
v[13]
=26
v[14]
=67
66
HEAPSORT: percolazione (sift)
•
CONSIDERIAMO UNO HEAP IN CUI MANCHI L'ELEMENTO DI INDICE 0
E PENSIAMO DI INSERIRE UN NUOVO ELEMENTO.
METTENDOLO IN POSIZIONE 0, QUELLO CHE SI OTTIENE E' UNO
HEAP?
 CIOE' E' h[0]h[1] E h[0]h[2] ?
•
SE NO, BISOGNA FARLO PERCOLARE AL POSTO GIUSTO:
• Se h[2] < h[0]  h[1] ALLORA BISOGNA SCAMBIARE h[0] E h[2] E
POI HEAPIFICARE RICORSIVAMENTE IL SOTTOALBERO DI
RADICE h[2].
• Se h[1]< h[0] h [2] ALLORA BISOGNA SCAMBIARE h[0] E h[1] E
POI HEAPIFICARE RICORSIVAMENTE IL SOTTOALBERO DI
RADICE h[1].
• Se h[0] > h[1]  h[0] > h[2] ALLORA BISOGNA SCAMBIARE h[0] E
min(h[1], h[2]) E POI HEAPIFICARE RICORSIVAMENTE IL
SOTTOALBERO DI RADICE h[1] O h[2] MODIFICATO.
• PERCHE' SIA MANTENUTA LA PROPRIETA' DELLO HEAP SI DEVE
HEAPIFICARE VERSO IL FIGLIO MINORE!
•
OVVIAMENTE TUTTI I DISCORSI SI POSSONO FARE IN MODO DUALE
67
PER HEAP IN CUI VALE LA RELAZIONE  ANZICHE' .
Percolazione : esempio
v[0]=
v[1]=42
v[3]=55
v[2]=6
v[4]=94
v[5]=18
v[6]=12
• facciamo percolare in v l'elemento 44
68
Percolazione : esempio
v[0]=44
v[1]=42
v[3]=55
v[2]=6
v[4]=94
v[5]=18
v[6]=12
• facciamo percolare in v l'elemento 44
69
Percolazione : esempio
v[0]=6
v[1]=42
v[3]=55
v[2]=44
v[4]=94
v[5]=18
v[6]=12
• facciamo percolare in v l'elemento 44
70
Percolazione : esempio
v[0]=6
v[1]=42
v[3]=55
v[2]=12
v[4]=94
v[5]=18
v[6]=44
• facciamo percolare in v l'elemento 44
71
HEAP: procedura di percolazione o sift()
•
•
fa percolare in un vettore heapificato dall'elemento di indice i+1 fino
all'elemento di indice r un elemento inserito nella posizione i
la percolazione termina quando un nodo non ha figli o e' minore o uguale
di tutti (1 o 2) i suoi figli
void sift (int n, int v [], int i, int r) {
// int v[n]; 0<=i<=n-1; 0<=r<=n-1; i<=r
// N.B.: n in effetti e' irrilevante, conta solo r
int j = 2*i+1; // indice di eventuale figlio sx
if (j<=r) {
// esiste almeno il figlio sx?
if (j<r && v[j]>v[j+1]) j += 1; // e il dx?
// j e' l'indice del figlio con valore minore
// se v[j]<v[i] li scambia e percola ricors.
if (v[i]>v[j]) {
// scambia v[i] e v[j]
}
int tmp = v[i]; v[i] = v[j]; v[j] = tmp;
sift(n, v, j, r); // percola ricorsivamente
} // end if
} // end if
72
HEAPSORT : procedura di sift()
• procedura di sift()
• CORRETTEZZA: E' DIMOSTRATA FACILEMENTE PER
INDUZIONE MATEMATICA sull'altezza del nodo da cui si fa
percolare,
•
•
TENENDO CONTO CHE SE i*2+1>r IL SOTTOALBERO DI
RADICE i, CHE CONTIENE SOLO L'ELEMENTO i, E'
OVVIAMENTE UNO HEAP, E
•
ASSUMENDO CHE TUTTI GLI ELEMENTI DI INDICE >i
SIANO RADICI DI SOTTOALBERI HEAP
COMPLESSITA': E' LINEARE CON L'ALTEZZA NELL'ALBERO
DEL NODO DI INDICE i, IN QUANTO E'
T(altezza) = T(altezza-1) + cost
73
HEAPSORT: heapificazione iniziale
• Per applicare la strategia delineata bisogna inizialmente heapificare
l'intero vettore in ingresso (che, in generale, non e' uno heap).
• In realta', qualsiasi vettore di dimensione n e' gia' intrinsecamente
uno heap per tutti gli elementi di indice i>n/2-1, per i quali non esiste
nessun elemento 2*i+1 e 2*i+2 con cui confrontarsi!
• Per heapificare il resto del vettore:
void buildHeap(int v[], int n) {
// int v[n]
int k = n/2-1;
// v[] e' gia' heapificato nel suffisso k+1..n-1:
// - j=k+1..n-1 : 2*j+1n-1  v[j]v[2*j+1]
// - j=k+1..n-1 : 2*j+2n-1  v[j]v[2*j+2]
while (k>=0) {
sift(n, v, k, n-1);
k -= 1;
}
}
74
HEAPSORT: heapificazione iniziale
•
buildHeap(), correttezza:
– La dimostrazione di correttezza (per induzione matematica)
e' banale tenendo conto della correttezza di sift() e
notando che quando sift-iamo l'elemento k tutti i successivi
sono gia' heapificati.
• buildHeap(), complessita':
– Poiche' lo heap ha altezza log(n), essendo un albero binario
completo o quasi completo, e poiche' la procedura sift()
e' invocata n/2 volte, buildHeap() e' di complessita' al
piu' O(n*log(n)).
– Vedi esercizi.
75
HEAPSORT: l'algoritmo
• Dopo l'applicazione di buidHeap() v[0] e' l'elemento
minimo che vogliamo estrarre:
 Dove lo mettiamo?
 Al posto dell'elemento in posizione v[n-1].
• Poi mettiamo il valore che era precedentemente in v[n-1] in
v[0] e lo facciamo percolare al posto giusto utilizzando la
funzione sift(), e tenendo conto che lo heap si e' accorciato
di un elemento.
• Ripetiamo questa operazione n-1 volte e il vettore e' ordinato.
 Ma e’ ordinato in modo non crescente!
• Per ordinare il vettore in modo non descrescente avremmo
dovuto costruire lo heap utilizzando la relazione  anziche la
relazione .
76
Heapsort: la strategia
•
Situazione all'i-esima iterazione del ciclo:
vettore v
v[0]
v[1]
...
v[i]
v[i+1] .. v[N-1] ordinato
i
v[i+i]..v[N-1] tratto del vettore gia' globalmente ordinato in
modo non crescente.
Tutti gli elementi del sottovettore v[i+1]..v[N-1]
sono minori o uguali di tutti gli elementi del
sottovettore v[0]..v[i]
v[0]..v[i]
sottovettore strutturato ad heap secondo la
relazione 
i
posizione nel vettore nella quale andare ad
inserire l'elemento minimo selezionato nel
sottovettore heap
77
HEAPSORT: l'algoritmo
void heapSort(int n, int v[]) {
int k;
buildHeap(v, n);
// v[0]..v[k] e' uno heap con relazione 
// j=k+2..n-1 : v[j-1]v[j]
// j=0..k, i=k+1..n-1 : v[j]v[i]
for(k=n-1; k>=1; k-=1) {
int temp = v[0];
v[0] = v[k];
v[k] = temp;
sift(n, v, 0, k-1);
}
}
78
HEAPSORT: correttezza e complessita'
• Correttezza:
IL VETTORE E' ORDINATO IN MODO NON CRESCENTE
Dimostrazione: e' per induzione sulle iterazioni.
L'IPOTESI INDUTTIVA E' CHE ALL'ITERAZIONE DI INDICE i
IL SOTTOVETTORE v[i+1..n-1] E' ORDINATO IN QUESTO
MODO, E CHE I SUOI ELEMENTI SONO TUTTI  DI QUELLI
DEL SOTTOVETTORE v[0..i]
• Complessita':
•
buildHeap() E' O(n*log(n)), COSI' E' OVVIAMENTE
ANCHE IL RESTO PER CUI TUTTO L'ALGORITMO E'
O(n*log(n)) ED E' IN-PLACE
• OVVIAMENTE SE VOGLIAMO UN VETTORE ORDINATO
IN MODO NON DECRESCENTE NON SCAMBIAMO GLI
ELEMENTI DOPO HEAPSORT, MA CAMBIAMO DA  A 
LA RELAZIONE CARATTERIZZANTE DELLO HEAP
79
Ordinare senza confrontare
• Si e' visto che operando per confronto non e' possibile ordinare un
vettore in tempo migliore che O(n*log(n)).
• Ma come e' possibile ordinare un vettore senza eseguire confronti?
• Come si fa a ordinare un mazzo di carte?
• Di solito per prima cosa si separano cuori, fiori, quadri e picche, e
per fare questo non si opera alcun confronto.
• I confronti entrano in gioco per ordinare tra loro carte dello stesso
seme.
 Che sono normalmente ordinate utilizzando straight insertion.
• Questo algoritmo ci dice che e' possibile ordinare non solo per
confronti, ma anche "per distribuzione".
• E' possibile operare solo per distribuzione?
80
Ordinare per distribuzione
L’algoritmo:
• Prima distribuisco le carte secondo il loro valore (numero),
indipendentemente dal colore, in 13 pacchetti diversi e ordinati tra loro.
 Il pacchetto dei 2 segue quello degli assi e precede quello dei 3.
• Poi raccolgo i pacchetti mantenedo il loro ordine.
• Poi distribuisco le carte cosi' raccolte in base al seme, in 4 pacchetti
diversi e ordinati tra loro.
• Poi raccolgo i pacchetti nel loro ordine: il mazzo risulta ordinato!
Note:
• La sequenza con cui si applicanoi criteri di distribuzione e’ essenziale:
• Se avessi distribuito al primo giro in base al colore e al secondo in
base al numero non avrei ottenuto un mazzo ordinato.
• Avrei ottenuto un mazzo con tutti gli assi, seguiti da tutti i 2, seguiti
da tutti i 3, … ogni sottomazzetto di egual numero ordinato secondo
il colore!
• Per ottenere il mazzo ordinato devo distribuire prima in base alla “cifra”
piu’ leggera (il numero), poi in base a quella piu’ pesante (il colore).81
RADIX SORT (Distribution Sort)
void radixSort(int n, int numLen, char* v[]) {
//
//
//
//
//
//
//
Un intero e' rappresentato
di caratteri in base 10.
Tutte le stringhe hanno la
numLen (>= 1).
Per unificare la lunghezza
dove necessario sono stati
leading 0
come una stringa
stessa lunghezza,
delle stringhe,
aggiunti dei
struct distributionSlot {
int
elsInSlot;
char* slot[?]; // cosa e'? See next page.
}
(struct distributionSlot) radixBins[10];
// un bidone per radice, cioe' per cifra
82
char*
• Cosa significa
slot[?] ?
char* slot[?]; ?
• Con questa notazione indichiamo un array di dimensioni
indefinite, che possono crescere (e calare?) secondo necessita'
(e.g. quando scriviamo un valore in un elemento non ancora
esistente).
• Una struttura dati di questo tipo non esiste come primitiva del C!
• A un certo punto ci dovremo quindi chiedere: come realizzarla?
• Nota che la modalita' di realizzazione dovra' garantire che il
costo delle operazioni sulla struttura dati sia quello che
ipotizzeremo per valutare la complessita' di radixSort()
• Nello scrivere radixSort() dovremo quindi porre attenzione
a quali operazioni sono necessarie per manipolare un oggetto di
tipo: char* slot[?]
83
RADIX SORT (Distribution Sort)
// reset distribution bins
for (int dScan = 0; dScan <= 9; dScan += 1)
radixBins[dScan].elsInSlot = 0;
// end for
// distribute/collect for each digit, from
// least significant
for (dScan = numLen-1; dScan>=0; dScan -= 1) {
// gli elementi in v sono ordinati rispetto
// al loro suffisso dScan+1..numLen-1
// distribute
for (int sScan = 0; sScan < n; sScan += 1) {
int iSlot = v[sScan][dScan] - '0';
int last = radixBins[iSlot].elsInSlot;
radixBins[iSlot].slot[last] = v[sScan];
radixBins[iSlot].elsInSlot += 1;
}
84
RADIX SORT (Distribution Sort)
// collect
// gli elementi in ogni slot sono ordinati
// rispetto al loro suffisso dScan+1..numLen-1
int sScan = 0;
for (int cScan = 0; cScan <= 9; cScan += 1) {
for(int iScan = 0;
iScan < radixBins[cScan].elsInSlot;
iScan += 1) {
v[sScan]= radixBins[cScan].slots[iScan];
sScan += 1;
}
radixBins[cScan].elsInSlot = 0;
}
// gli elementi in v sono ordinati
// rispetto al loro suffisso dScan..numLen-1
}
}
85
RADIXSORT: correttezza - 1
La procedura ordina le stringhe numeriche in ingresso in modo non
decrescente.
Dimostrazione: e' per induzione sulle iterazioni del ciclo di
distribuzione/raccolta, cioe' in pratica sulla lunghezza delle stringhe.
• Per stringhe di lunghezza 1 (numLen=1) il ciclo viene eseguito
una sola volta:
•
tutte le stringhe "0" sono sistemate nel bidone 0,
tutte le stringhe "1" sono sistemate nel bidone 1,
e cosi' via.
•
poiche' la fase di raccolta scandisce i bidoni in ordine da 0 a
9, nell'array finale tutte le stringhe "0" precedono tutte le
stringhe "1" che precedono tutte le stringhe "2" e cosi' via.
Continua alla pagina seguente.
86
RADIXSORT: correttezza - 2
• Supponiamo ora che la procedura operi correttamente per
stringhe di lunghezza n.
• Per ipotesi induttiva, dopo n iterazioni di distribuzione/raccolta
le stringhe sono ordinate nel vettore rispetto ai loro n ultimi
digit.
• L'n+1-esima iterazione processa le stringhe nell'ordine in cui
compaiono nel vettore, distribuendole in base alla n+1-esima
cifra dal fondo.
• Pertanto tutte le stringhe che hanno l'n+1-esimo digit che vale
'0' si trovano nel bidone 0, e all'interno del bidone queste
stringhe sono ordinate in base ai loro ultimi n digit.
• Lo stesso ragionamento si puo' fare per le stringhe il cui n+1esimo digit da destra vale '1', '2', …
• E poiche' la procedura di raccolta scandisce i bidoni e il loro
contenuto in ordine, anche il vettore di raccolta risultera'
ordinato, rispetto alle ultime n+1 cifre delle stringhe. QED
87
RADIXSORT: complessita‘ - prologo
Operazioni su char* slot[?]
• In che modo (con quali operazioni) sono accedute le strutture dati di
tipo char* slot[?]?
• Scritture (inserimenti) e letture/estrazioni in ordine FIFO
• E’ possibile tramite liste implementare una coda FIFO in cui le
operazioni di inserzione/rimozione hanno costo O(1)
• Quindi e’ legittimo assumere che anche le operazioni che accedono a
strutture dati char* slot[?] abbiano costo unitario.
• In realta’ durante la fase di collect sarebbe piu’ conveniente potere
raccogliere tutti gli elementi di un bidone tramite una unica operazione
di complessita’ costante (anziche’ trasferirli uno per uno).
 Perche’ questo sia possibile e’ sufficiente che tra le operazioni
sulla lista FIFO ci sia anche quella di concatenazione di liste e che
questa operazione abbia complessita’ costante!
88
RADIXSORT: complessita'
Complessita':
• il ciclo di distribuzione/raccolta viene ripetuto numLen volte,
cioe' tante volte quanto e' la lunghezza delle stringhe da
ordinare
• il corpo del ciclo ha complessita' O(n) dove n e' il numero di
stringhe da ordinare
 N.B.: trascurando le operazioni necessarie per scandire tutti
i bidoni.
Questa ipotesi e’ ragionevole se i bidoni sono normalmente
pieni, il che e’ probabilisticamente vero se il numero delle
stringhe (casuali) e’ molto maggiore di quello dei bidoni.
• per cui l'algoritmo ha complessita' O(numLen * n)
• ed e' conveniente rispetto agli algoritmi che operano per
confronto quando numLen<log(n)
• in realta' bisognerebbe tenere conto dei fattori moltiplicativi:
e.g. ad ogni iterazione ogni elemento e' copiato due volte!
89
RADIXSORT: complessita'
• Nota che piu’ bidoni ho a disposizione, piu’ rapido e’ l’algoritmo, perche’
a parita’ di lunghezza delle stringhe da ordinare il numero di fasi di
distribuzione-raccolta (pari al numero di cifre dei numeri) e’ minore.
 Dovendo ordinare un vettore di interi senza segno da 64 bit posso
utilizzare ad esempio radici da 4, 8, 16 bit (e corrispondentemente
16, 256, 65536 scatole): nel primo caso l’algoritmo effettuera’ 16
fasi, nel secondo 8, nel terzo 4.
• In realta’ pero’, detto #bins il numero dei bidoni utilizzati nella
distribuzione, la fase di raccolta ha complessita’ O(#bins+n)
perche’ devono essere scanditi tutti i bidoni, anche se sono vuoti.
• Normalmente si assume che sia n >> #bins, cosi’ che O(#bins+n) 
O(n), ma questo non e’ vero se #bins diventa molto grande.
• Da questo discende che non e’ sempre conveniente moltiplicare il
numero dei bidoni, e quindi diminuire numLen .
• In particolare non e’ detto che sia conveniente utilizzare tanti bidoni
quanti sono i caratteri dell’alfabeto in caso di stringhe Unicode (216
caratteri), salvo che il numero delle stringhe da ordinare non sia
90
comunque molto maggiore di 216.
RADIXSORT: generalizzazione
• L'algoritmo di radixsort puo' ovviamente essere generalizzato
anche a stringhe non numeriche e di lunghezza diversa:
• se consideriamo stringhe sull'alfabeto ASCII esteso (256
caratteri) quante radici dobbiamo considerare?
• Come si gestiscono stringhe di lunghezza diversa?
•
nel caso di stringhe numeriche basta considerarle
logicamente estese con degli 0 a sinistra
•
nel caso di stringhe alfabetiche basta considerarle
logicamente estese con degli spazi (o dei '\0') a destra
• Notare che la fase di raccolta puo' essere eliminata utilizzando 2
sequenze di bidoni di distribuzione e palleggiando le stringhe in
distribuzione dall'una all'altra
• Esercizio: riscrivere la procedura di distribution sort perche'
possa trattare stringhe alfanumeriche di lunghezza variabile ed
evitando la fase di raccolta
91
RankSort e sorting parallelo
(da: G. Stefanescu—National University of Singapore - Parallel & Concurrent Programming, Spring, 2004)
• Strategia dell’algoritmo di Rank Sort:
• count the number of numbers that are smaller than a number a in
the array
• this gives the position of a in the sorted array
• this procedure has to be repeated for all elements of the array
• Hence the time complexity of Rank Sort is n*(n-1), thus O(n2).
• Rank Sort e’ il peggiore algoritmo di ordinamento sequenziale visto nel
corso!
92
RankSort e sorting parallelo
• Versione sequenziale dell’algoritmo di Rank Sort:
void rankSort(int a[],int sorted[], unsigned n) {
/* works well only if there are no repetitions of
the numbers
* in the array
*/
for (unsigned i=0; i<n; i+=1) {
int rank = 0;
for (unsigned j=0; j<n; j+=1)
if (a[i] > a[j]) rank += 1;
sorted[rank] = a[i];
}
}
93
RankSort e sorting parallelo
• Versione parallela dell’algoritmo di Rank Sort, utilizzando n processori:
void rankSort(int a[],int sorted[], unsigned n) {
/* works well only if there are no repetitions of the
* numbers in the array
*/
forall (unsigned i=0; i<n; i+=1) {
/* l’istruzione parallela forall distribuisce
* l’esecuzione del ciclo su n processori paralleli
*/
int rank = 0;
for (unsigned j=0; j<n; j+=1)
if (a[i] > a[j]) rank += 1;
sorted[rank] = a[i];
}
}
• n processors work in parallel to find the ranks of all numbers of the
array.
• Parallel time complexity is O(n), better than any sequential sorting
94
algorithm.