Java algoritmi di ordinamento: Merge Sort

by Alessio Mungelli Date: 13-12-2019 java jdk jre sviluppo codice sorgente tutorial didattico spiegazione merge sort

Andiamo oggi ad analizzare uno tra i migliori algoritmi di ordinamento: il Merge Sort. Detto anche algoritmo per fusione, fa parte della famiglia dei Divide and Conquer proprio come il Quick Sort. A differenza del prima citato Quick Sort, il Merge Sort offre prestazioni migliori, siccome nella peggiore delle ipotesi la sua complessità rimane simile a O(n log n) mantenendo prestazioni ottimali.

L'unica pecca del Merge Sort è che necessita di strutture dati aggiuntive per poter svolgere le sue elaborazioni. Possiamo quindi dire che è un algoritmo stabile, ma non in-place. Inoltre è adattivo.

Funzionamento

Iniziamo guardando un'immagine esplicativa del funzionamento dell'algoritmo.

Merge Sort Scheme

Il funzionamento potrebbe essere già noto a chi ha già avuto a che fare con grandi collezioni di dati da ordinare. L'idea alla base è quella di dividere l'array in gruppetti e ordinarli. Una volta finita l'operazione di ordinamento dei singoli sottoinsiemi si prende il più piccolo tra gli elementi dei vari gruppi e inserirlo nel nuovo array. Si itera quindi questo processo sino ad esaurimento dei "mucchietti".

Il problema fondamentale è la fusione.

Algoritmo di fusione

  • Il semi-vettore sinistro è copiato su un vettore di appoggio;
  • Si seleziona il minimo tra il vettore di appoggio e il semi-vettore di destra e lo si copia sul vettore finale;
  • Si termina quando tutti gli elementi di appoggio sono stati copiati;

Implementazione

public class MergeSort 
{ 
    // Fonde due sottoarray di arr[]. 
    // il primo sottoarray è arr[l..m] 
    // il secondo sottoarray è arr[m+1..r] 
    public static void merge(int arr[], int l, int m, int r) { 
        // Trova le dimensioni dei due sottoarray da unire
        int n1 = m - l + 1; 
        int n2 = r - m; 

        /* Crea array temporanei */
        int L[] = new int [n1]; 
        int R[] = new int [n2]; 

        /*Copia i dati in array temporanei*/
        for (int index=0; index<n1; ++index) 
            L[index] = arr[l + i]; 
        for (int j=0; j<n2; ++j) 
            R[j] = arr[m + 1+ j]; 

        /* Unisce gli array temporanei */

        // Indici iniziali dei due array 
        int index = 0, j = 0; 

        // Indice iniziale del sottoarray finale
        int k = l; 
        while (index < n1 && j < n2){ 
            if (L[index] <= R[j]) { 
                arr[k] = L[index]; 
                index++; 
            } else{ 
                arr[k] = R[j]; 
                j++; 
            } 
            k++; 
        } 
        /* Copia gli elementi rimanenti di L[] se ce ne sono */
        while (i < n1) { 
            arr[k] = L[i]; 
            index++; 
            k++; 
        } 

        /* Copia gli elementi rimanenti di R[] se ce ne sono */
        while (j < n2) { 
            arr[k] = R[j]; 
            j++; 
            k++; 
        } 
    } 

    // Funzione principale che ordina arr[l..r] usando 
    // merge() 
    public static void sort(int arr[], int l, int r) { 
        if (l < r) { 
            // Trova il punto medio 
            int m = (l+r)/2; 

            // Ordina la prima e la seconda metà
            sort(arr, l, m); 
            sort(arr , m+1, r); 

            // Unisce le due metà 
            merge(arr, l, m, r); 
        } 
    } 

    public static void main(String args[]) { 
        int arr[] = {12, 11, 13, 5, 6, 7}; 

        System.out.println("Array da ordinare"); 
        System.out.println(Arrays.toString(arr));

        MergeSort.sort(arr, 0, arr.length-1); 

        System.out.println("nArray ordinato"); 
        System.out.println(Arrays.toString(arr));
    } 
} 

Capiamo il codice

Alcune note. Nei for è possibile omettere le parentesi graffe nell'eventualità che il corpo del ciclo contenga una sola istruzione. In questo caso, nei due for di copia dei dati nelle strutture temporanee è possibile omettere le parentesi graffe proprio perchè l'istruzione è una sola e non si presentano problemi relativi ad un eventuale ampliamento del codice.

Come nel Quick Sort ho reso i metodi statici in quanto non trovo utile utilizzare metodi dinamici che comporterebbero l'onere della creazione e gestione di un oggetto che li gestisca.

  • Metodo merge:

    Vengono calcolate le dimensioni dei due sottoarray e successivamente vengono istanziati. Dopodichè i due subset dell'insieme di partenza vengono copiati nelle due strutture ausiliarie. Dopodichè, riordina gli elementi rimettendoli nell'array originario. 
     
  • Metodo sort

    In questo metodo viene calcolato il punto medio del vettore che servirà per effettuare la divisione in sottoarray. E' importante utilizzare il punto medio per bilanciare il carico di elaborazione di ciascuna chiamata. Dopodichè vengono ordinate le due metà dell'array, rispettivamente di estremi (l, m) e (m+1, r).
    Infine vengono unite le due metà ordinate.
    La cosa importante è il controllo su l ed r. Questi due indici rappresentano i due estremi dell'array da ordinare. L indica l'estremo sinistro ed R l'estremo destro. Il problema è che, sotto particolari condizioni, l potrebbe diventare maggiore di r. Questo potrebbe creare situazioni inconsistenti e quindi si pone come condizione necessaria per l'esecuzione dell'intero procedimento l<r, evitando così al contempo errori di passaggio dei parametri e inconsistenza delle situazioni.
     
  • Main

    Questo main è piuttosto semplice. Viene infatti creata la collezione di dati da ordinare (un array di numeri interi in questo caso). Viene quindi richiamato il metodo sort passando come parametri l'array da ordinare e come indici 0 e n-1 (dove n indica la lunghezza dell'array).
    Si passa come estremo destro l'indice dell'effettiva ultima posizione perchè l'algoritmo itera in un intervallo del tipo [ 0 ; array.length ), che si può scrivere equivalentemente come [0 ; array.length-1 ] semplificando i controlli nei vari cicli.

Cenni sulla complessità

Complessità del processo di fusione

La complessità del processo di fusione ha crescita lineare, infatti ad ogni iterazione la dimensione dell'array finale cresce sempre di 1. E' quindi O(N).

C'è però un costo iniziale pari a O(N) per la copia del vettore di appoggio.

Costo dell'algoritmo

T(n) = 2T(n/2) + Theta(n)

Mediante opportuni passaggi algebrici è possibile giungere alla conclusione che la complessità dell'algoritmo è pari a Theta(nLogn).

Quando è utile Merge Sort?

Merge Sort risulta particolarmente utile quando si ha a che fare con Linked List proprio perchè l'inserimento ha complessità lineare. Siccome i nodi della lista non sono adiacenti, è particolarmente comodo utilizzare questo algoritmo.

 
by Alessio Mungelli Date: 13-12-2019 java jdk jre sviluppo codice sorgente tutorial didattico spiegazione merge sort visite : 6282  
 
Alessio Mungelli

Alessio Mungelli

Computer Science student at UniTo (University of Turin), Network specializtion, blogger and writer. I am a kind of expert in Java desktop developement with interests in AI and web developement. Unix lover (but not Windows hater). I am interested in Linux scripting. I am very inquisitive and I love learning new stuffs.

 
 
 

Articoli correlati

Come scaricare un'e-mail in formato PDF in Gmail per Android

Ora scoprirete quanto sia facile salvare un'e-mail ricevuta o inviata tramite Gmail in formato PDF, il tutto con il vostro smartphone Android. Gmail è una delle applicazioni di posta elettronica più…

Un approccio a Java: switch statement

Ciao a tutti e bentornati! Dopo una pausa, torniamo oggi con un'altra parte del corso introduttivo alla programmazione, parlando di switch statement, conosciuto anche come costrutto di selezione multipla.  Intuizione L'idea dello switch statement…

Un approccio a Java: Il ciclo while

Ciao a tutti e bentornati! Dopo aver fatto una breve, ma corposa, introduzione sui cicli, andiamo oggi a vedere finalmente le prime implementazioni che utilizzano quello che abbiamo definito ciclo precondizionale. In Java, come…

Un approccio a Java: I cicli - Introduzione

Ciao a tutti e bentornati! Sino ad ora, abbiamo parlato di variabili e di strutture di selezione, andando a considerare alcuni degli aspetti fondamentali di questi due concetti. Teoricamente, per…

Un approccio a Java: strutture di selezione - casi d'uso

Ciao a tutti e bentornati! Sino ad ora ci siamo preoccupati di fare una carrellata quanto più completa riguardo i concetti fondamentali di cui abbiamo bisogno per approcciarci all'utilizzo delle…

Un approccio a Java: operatori booleani

La volta precedente, abbiamo ampiamente parlato delle variabili booleane, cercando di delineare quali siano le principali operazioni che si possono effettuare proprio a livello pratico.  Di tutti i casi esaminati, non abbiamo…

Un approccio a Java: le variabili booleane

Ciao a tutti e bentornati! La volta precedente, ho fatto un'introduzione alle strutture condizionali, definendo il loro funzionamento. Prima di poter dare qualche esempio pratico, è necessario chiarire in che modo ci…

Un approccio a Java: strutture condizionali

Ciao a tutti e bentornati! Le volte precedenti abbiamo introdotto il concetto di variabile, tentando di definire alcuni concetti basilari a riguardo.  Alcune situazioni fanno però intuire come il solo concetto…

Un approccio a Java: Le variabili - caso d'uso

Ciao a tutti amici e bentornati! Dopo l'introduzione fatta sulle variabili, cerchiamo di analizzare alcune criticità che si possono presentare in situazioni alquanto comuni. Partiamo quindi analizzando degli esempi pratici.  Esempio 1: divisione…

Un approccio a Java: Le variabili

Ciao a tutti e bentornati! Quest'oggi inizieremo un percorso che ci porterà a studiare, ed eventualmente ripassare, quelle che sono le basi della programmazione. Inizieremo parlando di variaibli. Introduzione Chiunque voglia approcciarsi al…

Hashmap con Concatenamento: hashing, collisioni e prime funzioni

Oggi andremo a vedere dei concetti strettamente legati alle hashmap. I concetti che andremo a vedere sono quelli di hashing e collisioni. Hashing L'idea dell'hashing con concatenamento è quella di creare una sorta di array di…

Hashmap con concatenamento: liste di trabocco

In questa breve serie di articoli andremo a vedere com'è possibile realizzare in C la struttura dati Hashmap. Nell'implementazione andremo ad usare le liste doppiamente concatenate come strutture dati ausiliarie. Andiamo…