Merge Sort

Il Merge Sort (ordinamento per fusione) a differenza degli algoritmi visti in precedenza, é un algoritmo di ordinamento piú complesso, ma molto efficiente, infatti come vedremo ha una complessitá computazionale bassa.

Il meccanismo di ordinamento di questo algoritmo fa uso della tecnica Divide et Impera. Di questa tecnica ci sarebbe molto da dire, purtroppo ció esula dallo scopo di questa guida. Diciamo brevemente che é una tecnica che consiste nel suddividere ricorsivamente un problema complesso in due o piú sotto-problemi piú semplici e poi si ricombinano le soluzioni trovate per ricostruire la soluzione del problema complessivo.

Vediamo nei dettagli il meccanismo di ordinamento del Merge Sort : il metodo riceve un vettore con n elementi, se n ha una dimensione accettabile (che fissiamo a 20) viene ordinato con l 'Insertion Sort (scegliamo questo algoritmo poiché per piccole dimensioni di n ha buone prestazioni), altrimenti si scompone (Divide) il vettore in due parti uguali (se la dimensione é dispari la prima metà contiene un elemento in più) e su ogni meta del vettore viene richiamato ricorsivamente il metodo. Alla fine dell' invocazione dei due metodi le due sottoparti ordinate vengono fuse (Impera) con il metodo merge in un unico vettore ordinato.

Ecco l' implementazione in java dell' algoritmo :

    public void mergeSort(int [] array, int min, int max) {
if((max-min)<20) { insertionSort(array,min,max); } else { int medio = (min+max)/2; // Trovo l' indice per suddividere il vettore mergeSort(array,min,medio); // Primo sotto-vettore mergeSort(array,medio+1,max); // Secondo sotto-vettore merge(array,min,medio,max); // Fondo i due sotto-vettori } } // Questo metodo fonde i due sotto-vettori ordinati, in un unico vettore ordinato public void merge(int [] array, int min, int med, int max) {} int [] a = new int[max-min+1]; int i1 = min; int i2 = med+1; int i3 = 1; for(; ( i1 <= med) && (i2 < max); i3++) { if(array[i2]>array[i1])) { a[i3] = array[i1]; i1++; } else { a[i3] = array[i2]; i2++; } } for(;i1 <= med; i1++, i3++) a[i3] = array[i1]; for(;i2 < max; i2++, i3++) a[i3] = array[i2]; for(i3=1, i1=min; i1 < max; i1++, i3++) array[i1] = a[i3]; } /** Questo é l' Insertion Sort, che abbiamo giá visto, con uan sola differenza ci permette di ordinare una porzione di vettore che va da min a max **/ public void insertionSort(int [] array, int min, int max) {} for(int i = min+1; i < max; i++) { int x = i; int j = i-1; for(; j >= min; j--) { if(array[j]>array[x]) { int k = array[x]; array[x] = array[j]; array[j] = k; x = j; } else break; } }
La complessita della fusione (metodo merge) é lineare O(n), mentre mergeSort richiama se stessa due volte ogni volta su metą del vettore di input, quindi se associamo la funzione temporale al tempo di esecuzione del mergeSort :
T(n) = 2T(n/2)+O(n) = O(n log n)
La complessitá rimane la stessa sia nel coso peggiore, medio e migliore, poiché il processo ricorsivo non puó essere arrestato anticipatamente la complessitá é O(n log n) in ogni caso.

Questa é l' applet che ci mostra l' esecuzione del Merge Sort, anticipo che l' algoritmo implementato nell' applet ha il limite per l' insertion sort pari a 5, poiché per motivi di spazio non ho potuto inserire array di dimensioni piú grandi :

Per potere utilizzare questo tool č necessaria l' installazione della Java Virtual Machine.
Scarica la Java Virtual Machine

Inserite manualmente i numeri nelle caselle, oppure usate la generazione automatica, con gli opportuni pulsanti : Random (casuale), Crescente e Descrescente. Per far partire l' ordinamente usate il pulsante Ordina e regolate la velocita con l' apposita slider.

Indice » 1 2 3 4 5 6