Laboratorio di didattica dell’informatica generale
Prof. Carlo Fusco
Algoritmi di ordinamento ricorsivi
Calzetta Emilia
Cervone Vincenzo
Coppola Maria
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Programmazione didattica
Titolo: Algoritmi di ordinamento ricorsivi
Classe: 3^ I.T.I.S.
Contenuti: Significato dell’ordinamento; Ripetizione dei concetti di Iterazione
ricorsione, Algoritmi ricorsivi (quick-sort, merge-sort); Analisi e comparazione
degli algoritmi; Implementazione degli algoritmi con le macro di Excell
Prerequisiti:
Conoscenze sull’organizzazione dei dati mediante la struttura vettoriale
Conoscenze della teoria della ricorsione e dell’iterazione
Conoscenze della teoria e implementazione degli algoritmi
Conoscenze delle macro di Excel
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Programmazione didattica
Obiettivi:
Saper gestire l’organizzazione e ordinamento dei dati in un vettore
Capire l’importanza dell’ordinamento dei dati
Utilizzare le strutture di iterazione e ricorsione
Analizzare le applicazioni relative agli argomenti teorici affrontati
Modalità di lavoro:
lezioni frontali
utilizzo del laboratorio
Riferimenti:
A. Lorenzi, D. Rossi- Basi teoriche dell’informatica: progettazione degli algoritmi
Atlas
Cormen, Leiserson, Rivest- Introduzione agli algoritmi -McGrawHill
A. Lorenzi, D. Rossi- Informatica teoria e programmazione in Visual Basic per le
Scuole superiori -Atlas
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Ordinamento di un vettore
Il problema dell’ordinamento crescente di un vettore (array) di interi è
caratterizzato come segue:
dato un vettore A di elementi interi, trasformarlo in modo tale che, per ogni indice
i, l’elemento A[i] sia minore o uguale di tutti gli altri elementi di dati di indice j,
con i<j
Esempio:
A = [10,2,13,4]
Vettore iniziale
A = [2,4,10,13]
Vettore ordinato
A[i] ≤ A[j] con i, j =1, …,4 , i<j
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Importanza dell’ordinamento
L’accesso a collezioni di dati ordinate in modo opportuno è più semplice
che non l’accesso a collezioni non ordinate.
•A che servirebbe un elenco telefonico se gli utenti fossero
elencati in ordine sparso?
•A che servirebbe un elenco telefonico se gli utenti fossero
elencati per numero telefonico crescente?
Anche nei calcolatori, è spesso utile gestire collezioni di dati ordinate
secondo un qualche criterio di ordinamento, questo ad esempio permette
di usare algoritmi di ricerca più efficienti (ricerca binaria)
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Problema: ordinare in ordine crescente una sequenza di studenti considerando
le chiavi di ordinamento: età, nome, media scolastica
Luca
18 anni
Media=5
Antonio
14 anni
Media=9
Gianni
17 anni
Media=8
Marco
16 anni
Media=7
Carlo
15 anni
Media=6
Ordinamento crescente per età
Antonio
14 anni
Media=9
Carlo
15 anni
Media=6
Università degli Studi di Napoli Parthenope
Marco
16 anni
Media=7
Gianni
17 anni
Media=8
Luca
18 anni
Media=5
SICSI V CICLO classe A042
Ordinamento crescente per nome
Antonio
14 anni
Media=9
Carlo
15 anni
Media=6
Gianni
17 anni
Media=8
Luca
18 anni
Media=5
Marco
16 anni
Media=7
Ordinamento crescente per media scolastica
Luca
18 anni
Media=5
Carlo
15 anni
Media=6
Università degli Studi di Napoli Parthenope
Marco
16 anni
Media=7
Gianni
17 anni
Media=8
Antonio
14 anni
Media=9
SICSI V CICLO classe A042
Iterazione e ricorsione
Gli algoritmi di ordinamento possono essere iterativi e ricorsivi
Iterazione: ripetere piu’ volte una sequenza di operazioni
Esempio: somma i primi n interi: ( ( ( (1)+ 2) +3)+…+ n)
for (i=1, i<=n, i++) somma=somma +i
La caratteristica fondamentale di un algoritmo ITERATIVO è che a ogni passo
è disponibile un risultato parziale: dopo k passi, si ha a disposizione il
risultato parziale relativo al caso k
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Iterazione e ricorsione
Gli algoritmi ricorsivi si basano sulla possibilità di definire una funzione in
termini di se stessa.
Una funzione è definita ricorsivamente quando nella sua definizione compare
un riferimento a se stessa.
Esempio: somma i primi n iteri
Sn= n + Sn-1
n + somma dei primi (n-1) numeri iteri
Risolvere un problema con un approccio ricorsivo comporta:
• identificare un “caso base” la cui soluzione sia nota
• riuscire a esprimere la soluzione al caso generico n in termini dello
stesso problema in uno o più casi più semplici (n-1, n-2, etc).
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Esempio di funzione ricorsiva:
Sn= n + Sn-1
somma dei primi n iteri
n + soluzione del problema della somma dei primi (n-1) iteri
“somma dei primi (n-1) interi” è una istanza più semplice del problema “somma
dei primi n interi” e tale istanza può essere scomposta, a sua volta, in un’istanza
ancora più semplice
Sn= n+(n-1)+Sn-2
Procedendo in queste scomposizioni si giunge fino all’istanza banale del
problema S1= 1
Sn= n+(n-1)+(n-2)+(n-3)+…+1
Osserviamo che nella ricorsione, a differenza dell’iterazione, non si dispone di
un risultato parziale finché non si è giunti fino all’istanza elementare
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Algoritmi di ordinamento ricorsivi
Il motto latino ‘Divide et Impera’ è stato acquisito dall’informatica come tecnica
per risolvere problemi complessi, in pratica si genera una sequenza di istanze
via via più semplici del problema, fino all'istanza che non è più suddivisibile e
che ha soluzione banale
Il Quick-sort e il Merge-sort sono due algoritmi di ordinamento ricorsivi che si
basano sulla tecnica ‘Divide et Impera’
“DIVIDE ET IMPERA”
Dividi e domina dicevano i latini: sia con il significato che una volta
conquistato un nuovo territorio è meglio tenere diviso il popolo, se è ostile,
per evitare rivolte e sovversioni; sia con il significato di
partizionare il territorio per amministrarlo meglio.
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Quick-sort (ordinamento veloce)
Il Quick-sort è uno degli algoritmi di ordinamento più diffusi, esso lavora
partizionando l’array da ordinare, e quindi ordinandone ricorsivamente ogni
partizione. Uno degli elementi dell’array viene scelto come valore di pivot (di
perno), i valori inferiori o uguali al pivot vengono messi alla sua sinistra, mentre
i valori superiori vengono messi alla sua destra.
Quindi il quick-sort è un algoritmo ricorsivo basato sul Divide et Impera:
Divide: si “partiziona” il vettore A[1…n] spostando i suoi elementi in due
sottovettori A[1…q-1] e A[q+1…n], separati da un elemento pivot A[q].
Ogni elemento di A[1…q-1] è  A[q];
Ogni elemento di A[q+1…n] è > A[q]
il pivot A[q] viene spostato nella posizione corretta del vettore ordinato
Impera: si ordinano ricorsivamente i due sottovettori A[1…q] e A[q+1…n] con
il Quick-sort, fino a generare vettori di 1 solo elemento (che sono banalmente
ordinati!)
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Pseudocodice del Quick-Sort
Indice mediano
Quick-Sort(A,s,d)
IF s < d
THEN q = Partiziona(A,s,d)
Quick-Sort(A,s,q-1)
Quick-Sort(A,q+1,d)
q è l’indice che divide il vettore A in due in modo che
gli elementi con indice  q siano minori o uguali a quelli con indice > q
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Pseudocodice del Quick-Sort
Quick-Sort(A,s,d)
Ordinamento dei
due sottoarray
IF s < d
THEN q = Partiziona(A,s,d)
Quick-Sort(A,s,q-1)
Quick-Sort(A,q + 1,d)
Poiché il primo sottovettore ha elementi tutti minori o uguali a quelli
del secondo sottovettore, basta ordinare separatamente i due
sottovettori per risolvere l’intero problema
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Pseudocodice del Quick-Sort
passo Divide
Quick-Sort(A,s,d)
IF s < d
THEN q = Partiziona(A,s,d)
Quick-Sort(A,s,q-1)
Quick-Sort(A,q++1,d)
1,d)
Quick-Sort(A,q
passo Impera
Divide: Partiziona è la chiave dell’algoritmo!
Impera: si ordinano ricorsivamente i due sottovettori
A[s…q] e A[q+1…d] con Quick-Sort
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Quick-Sort: Partiziona(A,s,d)
Partiziona(A,s,d)
x = A[d]
i = s - 1
j = s
WHILE j < d DO
Scegliamo come pivot (perno)
l’ultimo elemento dell’array e poi
spostiamo gli elementi maggiori del
pivot verso destra e gli elementi
minori verso sinistra.
IF A[j]  x
THEN i=i+1
“scambia A[i] con A[j]”
j = j+1
“scambia A[i+1] con A[d]”
RETURN i+1
L’indice
mediano
q
dipende
dall’elemento
è il numero di elementi minori o uguali al pivot
Università degli Studi di Napoli Parthenope
pivot:
SICSI V CICLO classe A042
Quick-Sort: Partiziona(A,1,12)
Scegliamo come elemento di pivot l’ultimo elemento dell’array da ordinare
pivot
Partiziona(A,s,d)
1
x = A[d]
2
3
4
5
6
7
8
9
10
11
x
12
20 14 28 34 15 45 12 30 21 25 16 22
i = s - 1
j = s
i j
WHILE j < d DO
IF A[j]  x
THEN i=i+1
“scambia A[i] con A[j]”
j = j+1
“scambia A[i+1] con A[d]”
RETURN i+1
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Quick-Sort: Partiziona(A,1,12)
x
Partiziona(A,s,d)
x = A[d]
1
2
3
4
5
6
7
8
9
10
11
12
i = s - 1
20 14 28 34 15 45 12 30 21 25 16 22
j = s
i
j
WHILE j < d DO
IF A[j]  x
THEN i=i+1
“scambia A[i] con A[j]”
j = j+1
“scambia A[i+1] con A[d]”
RETURN i+1
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Quick-Sort: Partiziona(A,1,12)
x
Partiziona(A,s,d)
x = A[d]
1
2
3
4
5
6
7
8
9
10
11
12
20 14 28 34 15 45 12 30 21 25 16 22
i = s - 1
j = s
i
j
WHILE j < d DO
IF A[j]  x
THEN i=i+1
“scambia A[i] con A[j]”
j = j+1
“scambia A[i+1] con A[d]”
RETURN i+1
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Quick-Sort: Partiziona(A,1,12)
x
Partiziona(A,s,d)
x = A[d]
1
2
3
4
5
6
7
8
9
10
11
12
20 14 28 34 15 45 12 30 21 25 16 22
i = s - 1
j = s
i
j
WHILE j < d DO
IF A[j]  x
THEN i=i+1
“scambia A[i] con A[j]”
j = j+1
“scambia A[i+1] con A[d]”
RETURN i+1
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Quick-Sort: Partiziona(A,1,12)
x
Partiziona(A,s,d)
x = A[d]
1
2
3
4
5
6
7
8
9
10
11
12
20 14 28 34 15 45 12 30 21 25 16 22
i = s - 1
j = s
i
j
WHILE j < d DO
IF A[j]  x
THEN i=i+1
“scambia A[i] con A[j]”
j = j+1
“scambia A[i+1] con A[d]”
RETURN i+1
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Quick-Sort: Partiziona(A,1,12)
x
Partiziona(A,s,d)
x = A[d]
1
2
3
4
5
6
7
8
9
10
11
12
15 34 15
28 45 12 30 21 25 16 22
20 14 28
i = s - 1
j = s
i
WHILE j < d DO
IF A[j]  x
j
j
Scambia 15 e 28
THEN i=i+1
“scambia A[i] con A[j]”
j = j+1
“scambia A[i+1] con A[d]”
RETURN i+1
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Quick-Sort: Partiziona(A,1,12)
x
Partiziona(A,s,d)
x = A[d]
1
2
3
4
5
6
7
8
9
10
11
12
20 14 15 34 28 45 12 30 21 25 16 22
i = s - 1
j = s
i
j
WHILE j < d DO
IF A[j]  x
THEN i=i+1
“scambia A[i] con A[j]”
j = j+1
“scambia A[i+1] con A[d]”
RETURN i+1
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Quick-Sort: Partiziona(A,1,12)
x
Partiziona(A,s,d)
x = A[d]
1
2
3
4
5
6
7
8
9
10
11
12
20 14 15 12
34 28 45 34
12 30 21 25 16 22
i = s - 1
j = s
i
WHILE j < d DO
IF A[j]  x
j
j
Scambia 34 e 12
THEN i=i+1
“scambia A[i] con A[j]”
j = j+1
“scambia A[i+1] con A[d]”
RETURN i+1
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Quick-Sort: Partiziona(A,1,12)
x
Partiziona(A,s,d)
x = A[d]
1
2
3
4
5
6
7
8
9
10
11
12
20 14 15 12 28 45 34 30 21 25 16 22
i = s - 1
j = s
i
j
WHILE j < d DO
IF A[j]  x
THEN i=i+1
“scambia A[i] con A[j]”
j = j+1
“scambia A[i+1] con A[d]”
RETURN i+1
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Quick-Sort: Partiziona(A,1,12)
x
Partiziona(A,s,d)
x = A[d]
1
2
3
4
5
6
7
8
9
10
11
12
21 45 34 30 28
20 14 15 12 28
21 25 16 22
i = s - 1
j = s
i
WHILE j < d DO
IF A[j]  x
j
j
Scambia 28 e 21
THEN i=i+1
“scambia A[i] con A[j]”
j = j+1
“scambia A[i+1] con A[d]”
RETURN i+1
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Quick-Sort: Partiziona(A,1,12)
x
Partiziona(A,s,d)
x = A[d]
1
2
3
4
5
6
7
8
9
10
11
12
20 14 15 12 21 45 34 30 28 25 16 22
i = s - 1
j = s
i
j
WHILE j < d DO
IF A[j]  x
THEN i=i+1
“scambia A[i] con A[j]”
j = j+1
“scambia A[i+1] con A[d]”
RETURN i+1
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Quick-Sort: Partiziona(A,1,12)
x
Partiziona(A,s,d)
x = A[d]
1
2
3
4
5
6
7
8
9
10
11
12
16 34 30 28 25 16
45 22
20 14 15 12 21 45
i = s - 1
j = s
i
j
j
WHILE j < d DO
IF A[j]  x
Scambia 45 e 16
THEN i=i+1
“scambia A[i] con A[j]”
j = j+1
“scambia A[i+1] con A[d]”
RETURN i+1
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Quick-Sort: Partiziona(A,1,12)
x
Partiziona(A,s,d)
x = A[d]
i = s - 1
1
2
3
4
5
6
7
8
9
10
11
12
22 30 28 25 45 34
20 14 15 12 21 16 34
22
j = s
i
WHILE j < d DO
j
Sposta il pivot
IF A[j]  x
THEN i=i+1
“scambia A[i] con A[j]”
j = j+1
“scambia A[i+1] con A[d]”
RETURN i+1
Università degli Studi di Napoli Parthenope
l’elemento di pivot (22)
è stato spostato nella
posizione che occuperà
nel vettore ordinato
SICSI V CICLO classe A042
Quick-sort (ordinamento dei sottoarray)
22 30 28 25 45 34
20 14 15 12 21 16 34
Applica il QuickSort ai sottoarray
14
12 16
20 16
21
20 15
14 15
12 21
45
30 28 25 34
45 34
22
Pivot=16
14 15
12
14 12
15
16
20
Pivot=34
21
22
25
30
28
28
30 25
28 30
25
34
45
12 14 15 15 20 21 22 25 28 30 34 45
Vettore ordinato!
Il quick-sort è un algoritmo che non crea
nuovi vettori ma sposta gli elementi nel
vettore di input servendosi di locazioni di
memoria ausiliarie in numero fisso
Università degli Studi di Napoli Parthenope
QuickSort(A,p,n)
if p < n then
q := Partition(A; p; n)
QuickSort(A; p; q - 1)
QuickSort(A; q + 1; r)
endif
SICSI V CICLO classe A042
QuickSort: analisi di complessità
Il tempo di esecuzione di QuickSort dipende dall’input e dalla scelta
dell’elemento di pivot, in pratica dipende dal bilanciamento fra i sottovettori
costruiti dal Divide
•Il
caso migliore si verifica quando i sottovettori sono perfettamente
bilanciati, entrambi di dimensione n/2 Siccome l’array viene diviso in due ad
ogni passo e devono comunque essere esaminati tutti gli n elementi, il tempo
di esecuzione tende a (n logn), se n è la dimensione dell’array di input
•Il
caso peggiore si verifica quando un sottovettore è sempre di dimensione 1
(l’altro è quindi di dimensione n - 1). In questo caso il tempo di esecuzione
tende a (n2), cioè cresce al più come il quadrato della dimensione dell’array
di input
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Quick-sort (Caso peggiore)
Il caso peggiore si ha se il vettore in input è già ordinato e si sceglie come
pivot il minimo o il massimo degli elementi.
Supponiamo che l’array è ordinato. Se si decide di scegliere come pivot il
primo elemento della sequenza, e cioè l’elemento minore, si avrebbe che
l’array ha un elemento nella partizione di sinistra, e gli altri elementi
nell’altra, perché sarebbero tutti maggiori del pivot.
12 14 15 18 21 34 45
Ogni chiamata ricorsiva di quicksort ridurrebbe solo di un’unità la dimensione
dell’array da ordinare. Sarebbero quindi necessarie n chiamate ricorsive per
effettuare l’ordinamento, portando a un tempo di esecuzione dell’ordine di
(n2).
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Quick-sort (scelta del pivot)
Una soluzione a questo problema si può ottenere scegliendo a caso il pivot tra gli
elementi della sequenza.
La probabilità di selezionare proprio l’elemento più piccolo dell’array e’ ad ogni
passo uguale ad 1/n, cioè e’ inversamente proporzionale alla lunghezza
dell’array.
Quindi scegliendo a caso il pivot, anche se la sequenza è già ordinata, e se gli
elementi sono sufficientemente numerosi, risulta altamente improbabile che il
pivot scelto sia l’elemento più piccolo (o il più grande) e in questo caso il
problema si riconduce al caso medio, cioè al caso in cui i sottovettori sono
sempre di dimensioni diverse
Nonostante le cattive prestazioni nel caso peggiore, QuickSort è il miglior
algoritmo di ordinamento in media.
(tempo di esecuzione del caso migliore = tempo di esecuzione del caso
medio)
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Merge-sort (ordinamento per fusione)
Anche il Merge-sort è formulato ricorsivamente (divide et impera) ma a
differenza del Quick-sort usa una procedura di fusione per ottenere l’array
finale ordinato.
In pratica l’algoritmo Merge-sort divide ripetutamente il vettore di input a
metà, finché si generano segmenti contenenti uno o due componenti, poi
ciascun segmento viene ordinato e si effettua la fusione fra i segmenti in
sequenza inversa rispetto alla fase di divisione:
Se l’array ha due elementi, essi vengono confrontati e scambiati se
non sono ordinati
Se l’array ha più di due elementi lo si divide a metà (‘divide’) e si
ordinano i due array ottenuti usando lo stesso metodo ricorsivamente
(‘impera’). Infine gli array vengono fusi per formare l’array ordinato
(fusione)
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
MergeSort(A, p, r)
Esempio: Si A il vettore da ordinare
if p < r then
q := (p + r) / 2
Dividi a metà!
A
3 6 11 1 12 5
8
7
MergeSort(A; p; q)
MergeSort(A; q + 1; r)
Merge(A; p; q; r)
endif
Dividi a metà
3 6 11 1 12
35 68 117 1 12 5
ricorsivamente!
8
3 6 11 13 12
113 816 12
711351 6812
11751 812 75
6 5
7
8
7
Ogni array viene ordinato con un semplice confronto
tra i suoi due elementi!
11
3 5715
11
8 71
8 57 8
3 6 11
37
11
3 16 12
11
12
812
33 5166 8
11
1516 12
6 812
57 12
Università degli Studi di Napoli Parthenope
7
SICSI V CICLO classe A042
Fusione di due array ordinati
Dati due array B e C ciascuno con n1 e n2 componenti ordinate in ordine
crescente, si vuole ottenere un unico array D ordinato costituito dai n1+n2
elementi di B e C.
1.
Sia i l’indice per scandire B, j l’indice per scandire C e k l’indice
che usiamo per costruire l’array D
2.
Inizializziamo k=1, i=1, j=1
3.
Se B[i]<C[j] allora D[k]=B[i], incrementa i e k; altrimenti D[k]=C[j],
incrementa j e k;
4.
Ripetere il passo 3 finchè uno dei due array (o entrambi) non è
esaurito.
5.
Inserire gli elementi dell’array non ancora esaurito nelle posizioni
restanti di C
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Esempio fusione (Merge): Consideriamo i vettori ottenuti nella precedente
scomposizione
11
3 5715
11
8 71
8 57 8
3 6 11
37
11
3 16 12
11
12
812
33 5166 8
11
1516 12
6 812
57 12
1
5
3 6 11
7
7 8 12
8<12
Facciamo il merge dei due
vettori ottenuti! 5<7
7<12
1<3
3<11
6<11
1 3 5
6
7 8 11 12
Vettore ordinato!
5<66<7
8<11
11<12
1<5 3<5
7<11
Università degli Studi di Napoli Parthenope
Merge(B,C,D,n,m)
i=1,
i=1,
i=1,j=1,
j=1,
j=1,k=1
k=1
k=1
for i=1 to n do
B[i]<C[j] then
then
IfIf B[i]<C[j]
D[k]=B[i], i=i+1,
i=i+1, k=k+1
k=k+1
D[k]=B[i],
else
else
D[k]=C[j], j=j+1,
j=j+1, k=k+1
k=k+1
D[k]=C[j],
endif
endif
endfor
While j<=m do
D[k]=C[j], j=j+1,k=k+1
endwhile
SICSI V CICLO classe A042
Complessità Merge-sort
L’operazione dominante del merge-sort è la fusione di sottosequenze ordinate,
il costo di questo algoritmo di ordinamento dipende quindi da quante volte
viene eseguita la fusione e da quanto costa ciascuna operazione di fusione
Analizziamo il tempo di esecuzione:
Sia M(n) il numero di confronti, nel caso peggiore, che MergeSort
opera con un input di dimensione n.
Sia T(n) una funzione per il tempo di esecuzione dell’algoritmo, tale
che M(n)  T(n)
T(n) = 0, se n=1 questo e' il caso base ( se c’è un solo elemento nell’array non si
spende tempo)
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Nel caso n2, il numero dei confronti fatti per ordinare n elementi e' al più
uguale alla somma del numero di confronti fatti nel caso peggiore per
ciascuno dei seguenti passi dell’algoritmo:
1. Ordina la parte sinistra dell'array
2. Ordina la parte destra dell'array
3. Unisci (merge) le due parti in un array ordinato
Quindi: T(n) = T(n/2) + T(n/2) + n, se n2
Osserviamo che:
Il primo termine (T(n/2)), fissa un limite superiore al numero di confronti
necessari ad ordinare la parte sinistra dell'array, che consiste della metà degli
elementi dell'intero array.
Il secondo termine (T(n/2)), fissa un limite superiore al numero di confronti
necessari ad ordinare la parte destra dell'array.
L'ultimo termine (n), fissa un limite superiore ai confronti necessari a
comporre i due array ordinati di n componenti
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Esempio: sia n=8, come calcoliamo T(8)?
Dobbiamo scomporre la relazione fintanto che non arriviamo al passo base:
T(8) = 2T(4) + 8
T(4) = 2T(2) + 4
T(2) = 2T(1) + 2
T(1) = 0
A questo punto possiamo fare le opportune sostituzioni come segue:
T(1) = 0
T(2) = 2T(1) + 2 = 0 + 2
T(4) = 2T(2) + 4 = 4 + 4 = 8
T(8) = 2T(4) + 8 = 16 + 8 = 24
In questo caso, il merge-sort richiede al piu' 24 confronti per ordinare 8
elementi, M(8)24
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Dimostriamo che per n in generale risulta M(n)n.logn
Infatti: dall’equazione
T(n) = 2T(n/2) + n, n  2
T(1) =0
Per semplificare consideriamo n=2k, (k=log 2n):
T(2k ) = 2T(2k-1) + 2k = 4 T(2k -2 )+ 2.2k
=
8 T(2k -3 )+ 3.2k =…= 2i T(2k -i ) + i.2k
Quando i=log 2n si ha:
T(n)= 2 log n T(1) + n.logn = 0 + n.logn
Quindi il merge-sort richiede un tempo di esecuzione di al più n log n, se n è la
lunghezza dell’array da ordinare.
Il merge-sort è, per array di grandi dimensioni, è il più efficiente algoritmo di
ordinamento basato sui confronti, perché anche nel caso pessimo ha un tempo di
esecuzione di al più nlogn e non esistono algoritmi di ordinamento di array basati
sui confronti che hanno un tempo di esecuzione inferiore.
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Merge-sort VS Quick-sort
Il quick-sort suddivide il vettore in due sottovettori delimitati
dall’elemento ‘pivot’, l’algoritmo vorrebbe suddividere a ogni passo il
vettore in due sottovettori uguali ma non sempre ci riesce, al contrario
del merge sort che ogni volta spezza il vettore a metà.
In pratica il quick-sort riesce al più a
emulare il merge-sort, ma senza riuscire a
eguagliarlo in tutti i casi.
Dipende tutto dalla scelta del pivot!
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Prestazioni degli algoritmi di sorting
Le prestazioni degli algoritmi possono essere confrontate con diversi metodi. Uno
di questi consiste nella stima del tempo richiesto cioè nel valutare un limite
superiore al tempo di esecuzione del algoritmo. Dire che un algoritmo ha un
tempo di esecuzione di al più n2 significa che il suo tempo di esecuzione non cresce
più del quadrato della dimensione n del suo input
n
1
16
256
4.096
65.536
1.048.476
16.775.616
lg n
n lg n
n2
0
0
1
4
64
256
8
2.048
65.536
12
49.152
16.777.216
16 1.048.565
4.294.967.296
20 20.969.520 1.099.301.922.576
24 402.614.784 281.421.292.179.456
In questa tabella sono indicati i fattori di crescita delle varie
funzioni per la stima dei tempi degli algoritmi
Se i valori nella tabella rappresentano microsecondi, allora un algoritmo con un
tempo di esecuzione di al più (lgn) può impiegare 20 microsecondi per
processare 1.048.476 elementi, mentre un algoritmo che richiede un tempo di
esecuzione di al più( n2) può impiegare fino a 12 giorni!
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Prestazioni degli algoritmi di sorting (risultati
sperimentali)
Un altro modo per confrontare le prestazioni degli algoritmi di ordinamento
consiste, semplicemente, nell’eseguire molti test per ogni algoritmo al crescere
della dimensione n dell’input e nel confrontarne i tempi di esecuzione misurati.
Questi sono i risultati forniti da un programma (eseguito su un Pentium 3 di 500
MegaHertz) utilizzato per ordinare con diversi algoritmi un vettore di 30.000
elementi. I tempi sono nella forma minuti secondi.
Università degli Studi di Napoli Parthenope
SICSI V CICLO classe A042
Implementazione degli algoritmi di sorting
Analizziamo delle semplici simulazioni degli algoritmi di sorting che sono
state sviluppate con le macro di Microsoft Excel
Gli algoritmi di sorting si possono implementare in
svariati modi (Java, linguaggio C, Visual Basic,
etc.) noi abbiamo scelto il modo più semplice,
usando le macro di Excel. Questa scelta è mirata a
motivare l’interesse di tutti gli alunni, compresi
quelli che potrebbero ritenere ‘difficile’ l’uso di
metodi più sofisticati
Università degli Studi di Napoli Parthenope
Esempi
SICSI V CICLO classe A042