28 ottobre 2003 1

MergesortMergesort

F. Bombi

28 ottobre 2003

28 ottobre 2003

2

L’algoritmoL’algoritmo

L’algoritmo di ordinamento mergesort o per fusione è un algoritmo efficiente in quanto ha una complessità temporale O(nlog(n)) e può essere utilizzato per ordinare un vettore di oggetti Comparable oppure una lista o sequenza

L’algoritmo si basa sull’esistenza di un algoritmo efficiente in grado di fondere due vettori (o due liste) ordinate in un vettore (o in una lista) ordinata in un tempo O(n+m) essendo n ed m la lunghezza dei due vettori

28 ottobre 2003

3

Per ordinare un vettorePer ordinare un vettore

Dividere il vettore

s dc

2 147

s1 d1s2 d2

28 ottobre 2003

4

private void merge (int s1, int d1, int s2, int d2){ int i = s1; int j = s1; while (s1 <= d1 && s2 <= d2) if (v[s1].compareTo(v[s2]) < 0) tmp[i++] = v[s1++]; else tmp[i++] = v[s2++]; while (s1 <= d1) tmp[i++] = v[s1++]; while (s2 <= d2) tmp[i++] = v[s2++]; for (; j <= d2; j++) v[j] = tmp[j];}

Fusione di due arrayFusione di due array

28 ottobre 2003

5

AnalisiAnalisi

Ogni operazione elementare richiede un tempo costante, alla fine la lista l avrà una lunghezza pari a n+m e di conseguenza le operazioni necessarie sono n+m e quindi l’algoritmo ha una complessità O(n+m)

Il numero di confronti necessari è al minimo pari a n (oppure a m) se una delle due liste è composta da elementi minori degli elementi dell’altra lista, è invece O(n+m) se gli elementi delle due liste sono intercalati

L’algoritmo può essere usato per fondere due vettori parzialmente riempiti in un vettore ordinato con efficienza analoga, si utilizzeranno tre cursori per tenere traccia della posizione della testa dei due vettori d’origine e della posizione della coda nel vettore risultato

28 ottobre 2003

6

Per ordinare un vettorePer ordinare un vettore

Fondere due vettori

2 14

s1 d1s2 d2

Vettoretemporaneo

28 ottobre 2003

7

OrdinareOrdinare

Sia v l’array da ordinare

Siano i e s i cursori che definiscono inizio e fine dell’array

se l’array ha lunghezza > 1 dividere l’array in due metà individuate da i1, s1 e i2, s2

ordinare ricorsivamente da i1 a s1

ordinare ricorsivamente da i2 a s2

fondere le due parti dell’arrayNB: il caso base si ha quando

l’array ha lunghezza 0 o 1

28 ottobre 2003

8

private Comparable[] v;Private Comparable[] tmp;private int n;public void ordina (){ if (n > 1) { tmp = new Comparable[n]; ms(0, n-1); }}private void ms (int s, int d){ int c = (s + d)/2; if (s < c) ms(s, c); if (c+1 < d) ms(c+1, d); merge(s, c, c+1, d);}

NB: il codice effettua lechiamate ricorsive solo per array

di lunghezze maggiore di 1

28 ottobre 2003

9

8, 7, 6, 5, 4, 3, 2, 1

8, 7, 6, 5 4, 3, 2, 1

8, 7 6, 5 4, 3 2, 1

8 7 6 5 4 2 13

7, 8 5, 6 3, 4 1, 2

5, 6, 7, 8 1, 2, 3, 4

1, 2, 3, 4, 5, 6, 7, 8

Albero delle chiamate ricorsiveper un array di 8 elementi

28 ottobre 2003

10

Analisi di mergesortAnalisi di mergesort

Vogliamo dimostrare che mergesort ha una complessità temporale O(n log(n))

Supponiamo che ogni operazione sugli array richieda un tempo costante

Per semplicità supponiamo anche che la lunghezza n dell’array da ordinare sia una potenza di 2 e quindi si possa dire che

n = 2k

Analizziamo il tempo in funzione di k

28 ottobre 2003

11

A meno di costanti (inessenziali nella valutazione del comportamento asintotico dell’algoritmo) possiamo dire che:

T(k) = 2 T(k-1) + 2k

T(0) = 1La ricorrenza ha come soluzione

T(k) = (k+1)2k

Infatti questo è vero per k = 0, supponendo che sia vero per un valore qualsiasi di k= k’ avremo che

T(k’) = (k’+1) 2k’

28 ottobre 2003

12

Dobbiamo dimostrare che è veroT(k’+1) = (k’+1+1)2k’+1

Infatti dalla ricorrenza iniziale abbiamo:T(k’+1) = 2 T(k’+1-1) + 2k’+1

Dall’ipotesi fatta per k = k’ si ha:T(k’+1) = 2(k’+1)2k’ + 2k’+1

E quindi:T(k’+1) = (k’+1+1)2k’+1

Che era quanto volevamo dimostrare

Ora dato che k=log(n) abbiamo cheT(n) = n(log(n)+1) = O(n log(n))