2.08 Lezione 8
- Dividere l'array in due metà
- Ordinare ricorsivamente ogni metà
- Unire le due metà
La prima cosa da fare è una copia dell'array, successivamente utilizzo due puntatori:
-
i: parte dal primo elemento dell'array, fino ad arrivare all'elemento che è appena prima della metà -
j: parte dalla posizione appena dopo della metà fino ad arrivare alla fine dell'array.
Posso confrontare la posizione i con la posizione j, trovo il minore e lo metto alla prima posizione dell'array iniziale. Faccio avanzare j (che puntava all'elemento più piccolo del confronto precedente) e lo confronto nuovamente con i. Continuo in questo modo finchè non finisco gli elementi.
Ovviamente i due sottoarray devono essere ordinati
Nel caso ci siano due elementi uguali, si prende sempre quello del sottoarray di sinistra.
private static void merge(Comparable[] a, Comparable[] aux, int lo, int hi, int mid){
for(int j = lo; k <= hi; k++)
aux[k] = a[k]; //copia array
int i = lo, j = mid+1;
for(int k = lo; k <= hi; k++){
if(i > mid)
a[k] = aux[j++]; //se l'array di destra ha ancora elementi
else if(j > mid)
a[k] = aux[i++]; //se l'array di sinistra ha ancora elementi
else if(less(aux[j], aux[i]))
a[k] = aux[j++]; //se j è strettamente minore di i prendiamo j
else
a[k] = aux[i++]; //in tutti gli altri casi prendiamo i
}
}Implementazione del Merge
public class Merge{
private static void merge(...){
//codice precedente
}
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi){
if(hi <= lo) return; //ritorniamo quando i due estremi coincidono
int mid = lo + (hi - lo) / 2; //calcolo il mid
sort(a, aux, lo, mid); //ordino metà sinistra
sort(a, aux, mid+1, hi); //ordino metà destra
merge(a, aux, lo, mid, hi); //unisco le due metà
}
//metodo usato per avviare la ricorsione
public static void sort(Comparable[] a){
Comparable[] aux = new Comparable[a-length];
sort(a, aux, 0, a.length -1);
}
}Algoritmo completo
Essenzialmente, il mergesort, essendo ricorsivo, arriva, dividendo ogni metà in una rispettiva metà, a confrontare due elementi alla volta, per poi effettuare il merge prima di 1+1 = 2 elementi, poi 2+2 = 4 elementi, poi 4+4 = 8 elementi, poi 8+8 = 16 elementi e così via.
L'immagine ci mostra chiaramente che tutti gli elementi grigi non vengono confrontati, andando a risparmiare una notevole quantità di tempo.
Questo ci permette di vedere dalle indagini empiriche come si abbatte il tempo per quanto riguarda i milioni e miliardi in un array quando confronto insertion sort e mergesort:
| migliaia | milioni | Miliardi |
|---|---|---|
| istantaneo | 2.8 ore | 317 anni |
insertion sort N2
| migliaia | milioni | Miliardi |
|---|---|---|
| istantaneo | 1 secondo | 18 minuti |
Mergesort N log N
possiamo dimostrare che il mergesort utilizza al più N log N confronti per ordinare un array di linghezza N.
ricorrenza: C(N) <= C(ceil(N/2)) + C(floor(N/2)) + N per N > 1, con C(1) = 0.
Dipende dal tempo per ordinare la parte sinistra dell'array, la parte destra più il tempo per fare il merge.
Se scegliamo un numero di elementi che sia una potenza di 2: N = 2N possiamo riscrivere la ricorrenza come:
ricorrenza: D(N) = 2 D(N/2) + N per N > 1, con C(1) = 0.
Il **mergesort ** utilizza al più 6 N log N accessi agli array per ordinare un array di linghezza N.
Questo perchè dobbiamo fare 2 N accessi per fare la copia: per ogni elemento devo entrare una volta nell'array originale ed una volta nell'array copia.
Abbiamo inoltre 2 N accessi agli array per i confronti, ed in fine 2N per fare nuovamente la copia nell'array originale.
Ogni algoritmo che ha la seguente struttura:
public static void linearitmic(int N){
if (N == 0) return;
linearitmic(N/2); //risolvo metà del problema
linearitmic(N/2); //risolvo l'altra metà del problema
linear(N); //fa una quantità di lavoro lineare
}Utilizza un tempo N log N .
Ovviamente lo spazio da utilizzare, siccome viene utilizzato un array copia, l'ultimo passo dell'algoritmo deve essere tale da contenere tutti gli elementi N, di conseguenza ho bisogno di un array extra di dimensioni N; questo ci fa capire che l'overhead per quanto riguarda lo spazio è proporzionale ad N.
Si dice che un algoritmo di ordinamento sia in-place se utilizza meno di c log N spazio extra.
Infatti, il mergesort non è in-place, visto che abbiamo bisogno di più di c log N spazio.
Esempi di algoritmi di ordinamento in-place sono gli algoritmi:
- insertion sort
- selection sort
- shellsort
Si potrebbe pensare di usare un array ausiliaro di dimenzioni 1/2 N, in quanto ho metà dell'array da una parte e metà dall'altra.
Sviluppare un mergesort in-place.
Il primo miglioramento pratico che possiamo adottare è il cutoff, visto che l'insertion sort funziona bene su piccoli subarray, posso pensare di effettuare un cutoff, e quindi passare da mergesort ad insertion sort quando arriviamo ad un subarray di 10 item. Ovvero quando i due puntatori hanno una differenza pari al cutoff-1 vado a fare l'insertion sort.
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi){
if(hi <= lo + CUTOFF -1){
Insertion.sort(a,lo,hi);
return;
}
int mid = lo + (hi - lo) / 2; //calcolo il mid
sort(a, aux, lo, mid); //ordino metà sinistra
sort(a, aux, mid+1, hi); //ordino metà destra
merge(a, aux, lo, mid, hi); //unisco le due metà
}
//metodo usato per avviare la ricorsione
public static void sort(Comparable[] a){
Comparable[] aux = new Comparable[a-length];
sort(a, aux, 0, a.length -1);
}possiamo evitare il merging quando abbiamo la situazione:
A B C D E F G H I *J* *M* N O P Q R S T U V J<M
Siccome il sottoarray di sinistra è ordinato, ed il sottoarray di destra è ordinato (perchè sono stati ordinati per ricorsione precedentemente), faccio un confronto tra l'ultimo elemento del primo sottoarray ed il primo elemento del secondo sottoarray, se il primo è minore del secondo, è inutile fare il merge, ma semplicemente andare a mettere insieme (concatenare) i due sottoarray.
if(hi <= lo + CUTOFF -1){ //cutoff ad insertion sort
Insertion.sort(a,lo,hi);
return;
}
int mid = lo + (hi - lo) / 2; //calcolo il mid
sort(a, aux, lo, mid); //ordino metà sinistra
sort(a, aux, mid+1, hi); //ordino metà destra
if (!less(a[mid+1], a[mid])) return; // fermo se sono già ordinati
merge(a, aux, lo, mid, hi); //unisco le due metà
}entrambi gli accorgimenti implementati
Possiamo inoltre evitare la copia dell'array, cambiando il ruolo ogni volta tra a[] ed aux[]
private static void merge(Comparable[] a, Comparable[] aux, int lo, int hi, int mid){
for(int j = lo; k <= hi; k++)
aux[k] = a[k]; //copia array
int i = lo, j = mid+1;
for(int k = lo; k <= hi; k++){
if(i > mid)
aux[k] = a[j++]; //se l'array di destra ha ancora elementi
else if(j > mid)
aux[k] = a[i++]; //se l'array di sinistra ha ancora elementi
else if(less(aux[j], aux[i]))
aux[k] = a[j++]; //se j è strettamente minore di i prendiamo j
else
aux[k] = a[i++]; //in tutti gli altri casi prendiamo i
}
}Codice modificato: invertito l'assegnazione cambiando da a[] = aux[] ad aux[] = a[].
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi){
if(hi <= lo + CUTOFF -1){
Insertion.sort(a,lo,hi);
return;
}
int mid = lo + (hi - lo) / 2; //calcolo il mid
sort(aux, a, lo, mid); //ordino metà sinistra
sort(aux, a, mid+1, hi); //ordino metà destra
merge(a, aux, lo, mid, hi); //unisco le due metà
}Ovviamente dobbiamo scambiare le variabili anche in sort().
Questo è il metodo utilizzato da java per ordinare gli oggetti (Mergesort) :
- Cutoff ad insertion sort = 7.
- Si ferma se gli array sono già ordinati.
- Eliminare la copia dell'array ausiliario.
- iterare sull'array, effettuando il merging di subarray di grandezza 1.
- ripetere per sottoarray di grandezza 2, 4 ,8
public class MergeBU{
private static void merge(){---}
public static void sort(Comparable[] a){
int N = a.length;
Comparable[] aux = new Comparable[N];
for(int sz = 1; sz < N; sz = sz+sz)
for(int lo = 0; lo < N - sz; lo += sz+sz)
merge(a, aux, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}
}Questo algoritmo iterativo risulta essere circa il 10% meno efficiente del mergesort ricorsivo perchè ci sono più movimenti di dati.
Il natural mergesort va a sftuttare le sequenze che sono già ordinate ed effettuiamo il merge tra queste.
Se mi accorgo che non ci sono sequenze preordinate nell'array iniziale, posso usare un binary insertion sort (che presuppone che devo usare un tempo N, per via del fatto che ho N compares ed N exchanges), quindi creo delle sequenze ordinate di 2 elementi e quindi andare ad effettuare il merge.
Questo tipo di sort ha un tempo di completamento lineare per molti array che hanno un ordine pre esistente ed è molto usato in vari linguaggi di programmazione come Java e Python.
La complessità computazionale gioca un ruolo importante nella progettazione di algoritmi. Il primo passo nello studio della complessità è quello di stabilire il modello computazionale, che è dato dalle operazioni ammissibili. Per quello che riguarda l'ordinamento, studiamo la classe degli algoritmi basati sui confronti.
Questi algoritmi prendono le decisioni solo sulla base di confronti fra chiavi. Posso quindi ottenere informazioni su quale elemento deve andare prima e quale dopo, basandomi sul confronto. Un algoritmo basato su confronti può fare diverse compiutazioni tra un confronto e l'altro, ma non può ottenere informazioni sulle chiavi se non confrontando una chiave con un'altra.
Per quanto riguarda il modello di costo sappiamo che ci focalizziamo sul conteggio delle operazioni, o meglio le operazioni più frequenti.
L'upper bound ci dice quindi come si comporta l'algoritmo nel caso peggiore. Per un dato algoritmo x l'upper bound ci diche che 'x al più eseguirà con un tempo proporzionale a tot'.
La parte più impegnativa è quella di stabilire il lower bound, ovvero capire qual è il limite al di sotto del quale tutti gli algoritmi basati su confronti non possono spingersi.
- modello di computazione:
decision tree(può accedere alle informazioni solo tramite confronti) - cost model: numero di confronti
- Upper bound: ~N lg N dal mergesort
- Lower bound: ~N lg N
- Algoritmo ottimale = mergesort
Il goal principale della progettazione di algoritmi è quello di creare algoritmi ottimali, ovvero in linea con il lower bound
Possiamo costruire un albero binario per descrivere la sequenza di confronti per stabilire un dato ordinamento.
Se abbiamo 3 elementi distinti, avremo N! foglie, perchè dobbiamo calcolare le permutazioni di questi tre elementi.
Il modello computazionale si basa sul fatto che devo effettuare confronti fra tutti gli elementi. Ovviamente, un nodo interno corrisponde ad un'operazione di confronto fra gli elementi posizione i e j.
Per ogni nodo avremo un sottoalbero sinistro ed un sottoalbero destro. Il sottalbero sinistro rappresenta il fatto che il nodo di posizione i è minore del nodo di posizione j. In modo duale, il sottoalbero destro rappresenta il fatto che il nodo di posizione j è minore del nodo di posizione i.
Quindi ogni cammino dalla radice ad una foglia corrisponde alla sequenza di confronti che l'algoritmo usa per stabilire l'ordine dato dalla foglia.
Il numero di confronti è compreso tra il nbumero di computazioni possibili (6) e l'altezza dell'albero. Avrò bisogno al più di 3 confronti (in questo caso). Tenendo a mente l'albero sappiamo che il numero di permutazioni è N!, sappiamo che in un albero completo di altezza h abbiamo nh foglie, avremo che il caso peggiore è dettato dall'altezza h dell'albero.
- assumiamo che l'array consista di N valori diversi, da a1 ad aN
- Il caso peggiore è dato dall'altezza h dell'albero di decisione.
- L'albero binario di altezza h ha al massimo 2h foglie
- N! diversi ordinamenti -> almeno N! foglie
Per quanto riguarda i confronti l'algoritmo Mergesort è ottimale, ma non lo è se teniamo conto dello spazio, dato che utilizziamo dello spazio extra.
Possiamo ordinare degli elementi con diverse strategie, ad esempio in un eleneco di medagli di olimpiadi per ogni nazione possiamo ordinare per il numero di medaglie d'oro oppure al numero totale di medaglie, e questo ci da due ordinamenti diversi.
Possiamo avere quindi diversi ordinamenti in base a quello che scegliamo.
Se facciamo riferimento all'interfaccia comparable, dobbiamo tenere a mente che questa interfaccia è stata creata per stabilire un ordine naturale, ad esempio i numeri naturali, reali, le date. Se abbiamo esigenza di usare un ordine alternativo rispetto a quello naturale, possiamo usare l'interfaccia Comparator<>.
public interface Comparator<Key>
int compare(Key v, Key w);Interfaccia comparator
Per supportare i comparator nelle implementazioni di sort possiamo utilizzare Object e passiamo un Comparator:
public static void sort(Object[] a, Comparator comparator){
int N = <.length;
for(int i = 0; i<N; i++){
for(int j = i; j>0 && less(comparator, a[j], a[j-1]); j--)
exch(a, j, j-1);
}
}
private static boolean less(Comparator c, Object v, Object w){
return c.compare(v,w) <0;
}
private static void exch(Object[] a, int i, int j){
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}