Uno dei problemi tipici che spesso si deve affrontare quando si trattano collezioni di dati omogenei è l'ordinamento degli stessi.
Una collezione di dati ordinati semplifica notevolmente, ad esempio, le operazioni di ricerca di un elemento nella collezione.

Gli elementi di una collezione possono essere ordinati in due modi:

• per valori crescenti, ossia quando ogni elemento della collezione precede, ossia è inferiore secondo il criterio dell'ordinamento, tutti gli elementi successivi
• per valori decrescenti, ossia quando ogni elemento della collezione segue, ossia è maggiore secondo il criterio dell'ordinamento, tutti gli elementi successivi

Gli algoritmi per ordinare gli elementi di una collezione sono diversi e si distinguono per il numero di confronti ed il numero di scambi tra elementi, effettuati per completare l'operazione di ordinamento.

Ovviamente, minore sarà il numero di confronti e scambi di elementi e maggiore sarà l'efficienza dell'algoritmo stesso.
Un'altro elemento di distinzione è la necessità di memoria aggiuntiva (strutture dati aggiuntive) per svolgere il lavoro di ordinamento.
Gli algoritmi che non necessitano di strutture aggiuntive per eseguire l'ordinamento dei dati vengono anche detti algoritmi in-place.

Una ulteriore distinzione riguarda la strategia risolutiva.
Gli algoritmi che utilizzano strategie facilmente individuabili dal ragionamento umano sono detti algoritmi ingenui.
Quelli che invece utilizzano strategie risolutive più complesse, individuate a seguito di considerazioni e studi logico-matematici sono detti algoritmi evoluti.

Esistono, pertanto, diversi algoritmi di ordinamento dei dati che differiscono per gli aspetti finora elencati.
I principali sono:

• algoritmi ingenui
• ordinamento per selezione (selection sort)
• ordinamento per inserzione (insertion sort)
• ordinamento per scambio o a bolle (bubble sort)
• algoritmi evoluti
• ordinamento quicksort
• ordinamento shell sort
• ordinamento per fusione di collezioni ordinate (mergesort)

Di seguito esamineremo alcuni di essi approfondendone la logica ed implementandone la strategia in linguaggio Java.

L'algoritmo di ordinamento per selezione, noto anche con il nome di selection sort, appartiene alla categoria degli algoritmi ingenui, ossia la cui strategia risolutiva è alquanto naturale e banale.
Esso può essere definito in due varianti, ossia per selezione del minimo o del massimo.
Nel seguito esamineremo nel dettaglio la versione con selezione del minimo.
La versione con selezione del massimo è analoga, con qualche piccola variazione, facilmente intuibile una volta compresa la logica di funzionamento della versione con selezione del minino.

L'algoritmo di ordinamento per selezione del minimo conduce all'ordinamento dei dati della sequenza attraverso i passi descritti di seguito.

Il vettore viene attraversato dal primo all'ultimo elemento alla ricerca del valore minimo.
Individuata la posizione del valore minimo, esso viene scambiato con il primo elemento del vettore, in modo che occupi, da ora in avanti, la prima posizione della sequenza.
Successivamente si procede allo stesso modo, considerando la sequenza formata dagli elementi del vettore successivi al primo.
Il procedimento si ripete fino a quando la sequenza risultante è composta da un solo elemento, che per definizione è ordinata.

Cerchiamo di comprendere meglio quanto descritto, attraverso una rappresentazione grafica.

Supponiamo di dover ordinare il vettore seguente:

Sulla base dell'algoritmo descritto precedentemente, il vettore viene attraversato alla ricerca del valore mininmo.
Tale valore è individuato nel valore 1, alla posizione 4.

Esso viene scambiato con il primo valore della sequenza analizzata, in modo da occupare la posizione più a sinistra nella sequenza considerata.
L'operazione di scambio è di seguito rappresentata graficamente.

A questo punto la sequenza costituita dal primo elemento è sicuramente ordinata
Occorre pertanto ripetere l'operazione concentrandosi sulla sottosequenza costituita dagli elementi successivi al primo.

Ripentendo la sequenza di passi utilizzata finora, fino a quando la sottosequenza da ordinare risulta costutuita da un solo elemento, il vettore si modificherà come mostrato di seguito, fino a contenere gli elementi originari ordinati in ordine crescente.

Una implementazione, in linguaggio Java, di tale strategia di ordinamento è mostrata nel codice seguente:

public static void selectioSort(int[] v) { // selezione del minimo
    // ad ogni iterazione si posiziona il minimo 
    // nella prima cella della porzione di vettore
    // esaminata
    for (int i = 0; i < v.length - 1; i++) {
        // si imposta il minimo alla posizione
        // del primo elemento della sequenza
        int posMin = i;
        for (int j = i + 1; j < v.length; j++) {
            // se si trova un elemento più piccolo 
            // del minimo attuale, si cambia la
            // posizione del minimo
            if (v[j] < v[posMin]) {
                posMin = j;
            }
        }
        // se la posizione del minimo non è quella iniziale
        // occorre scambiare l'elemento alla posizione del 
        // minimo con quello iniziale
        if (posMin != i) {
            int t = v[i];
            v[i] = v[posMin];
            v[posMin] = t;
        }
    }
}

Lo stesso algoritmo può essere implementato nella versione con selezione del massimo.
In tal caso, si cerca la posizione dell'elemento massimo, che viene poi posizionato in fondo alla sequenza.
Il procedimento, quindi, si ripete considerando la sottosequenza composta dagli elementi della sequenza precedente, privata dell'ultimo elemento.
In questo caso il vettore ordinato viene costruito a partire dal fondo.

Vediamone una implementazione in linguaggio Java, realizzata apportando una piccola variazione al codice visto sopra.

public static void selectioSort(int[] v) { // selezione del massimo
    // ad ogni iterazione si posiziona il massimo 
    // nell'ultima cella della porzione di vettore
    // esaminata
    int length = v.length;
    while (length > 1) {
        // si imposta il massimo alla posizione
        // del primo elemento della sequenza
        int posMax = 0;
        for (int j = 1; j < length; j++) {
            // se si trova un elemento più grande 
            // del massimo attuale, si cambia la
            // posizione del massimo
            if (v[j] > v[posMax]) {
                posMax = j;
            }
        }
        // se la posizione del massimo non è quella finale della 
        // sequenza occorre scambiare l'elemento alla posizione  
        // del massimo con quello in coda alla sequenza
        if (posMax != length - 1) {
            int t = v[length - 1];
            v[length - 1] = v[posMax];
            v[posMax] = t;
        }

        // a questo punto il massimo della sequenza è posizionato
        // in fondo ad essa, per cui si diminuisce la lunghezza 
        // della sequenza ancora da ordinare e si itera nuovamente
        length--;
    }
}

L'algoritmo di ordinamento per inserzione itera su sottosequenze del vettore da ordinare che crescono, ad ogni iterazione, di un elemento.
Si inizia con la sottosequenza formata dal primo elemento del vettore, ordinata per definizione in quanto costituita da un solo elemento.
Si procede, poi, estendendo la precedente sottosequenza, attraverso l'inserimento dell'elemento che la segue, nella sua posizione corretta, traslando gli elementi successivi ad esso di una posizione verso destra.
Si ripete tale procedimento fino a quando non sono stati esaminati tutti gli elementi del vettore da ordinare.
Analizziamo meglio tale strategia attraverso un esempio grafico.

Supponiamo di dover ordinare il vettore seguente:

Si inizia considerando la sottosequenza formata dal primo elemento del vettore, che risulta ordinata, per ovvie ragioni.

Si procede poi considerando la sottosequenza ottenuta aggiungendo l'elemento seguente alla sottosequenza precedente e verificando la sua posizione corretta all'interno della sottosequenza.

Nel caso in esame, l'elemento si trova già nella sua corretta posizione, per cui non si effettuano spostamenti e si procede con l'iterazione successiva.

Questa volta l'elemento aggiunto non si trova nella sua posizione corretta. Occorre pertanto traslare verso destra tutti gli elementi maggiori dell'elemento aggiunto ed inserire quest'ultimo nella sua corretta posizione.

Anche questa volta l'elemento aggiunto non si trova nella sua posizione corretta. Si ripete pertanto lo stesso procedimento effettuato all'iterazione precedente.

Si continua in modo analogo per i restanti elementi della sequenza.

Una implementazione, in linguaggio Java, di tale strategia di ordinamento è mostrata nel codice seguente:

public static void insertionSort(int[] v) {
    for (int l = 1; l < v.length; l++) {
        int el = v[l];
        int p = l - 1;
        while (p >= 0 && v[p] > el) {
            v[p + 1] = v[p];
            p--;
        }
        if (p != l - 1) {
            v[p + 1] = el;
        }
    }
}

L'algoritmo di ordinamento a bolle o bubble sort è un algoritmo iterativo, che procede confrontando coppie di elementi adiacenti e scambiando tra loro i valori, qualora non fossero nell'ordine corretto.

Esso può processare il vettore in due modi, dal primo all'ultimo elemento oppure nella direzione inversa.

Nel primo caso gli elementi di peso maggiore della collezione vengono spostati verso la fine del vettore e, ad ogni iterazione, l'elemento maggiore verrà posizionato nell'ultima posizione della sequenza.

Nel secondo caso gli elementi di peso minore della collezione vengono spostati verso l'inizio del vettore e, ad ogni iterazione, l'elemento minore verrà posizionato nella prima posizione della sequenza.

Al termine dell'iterazione si ripete il procedimento sulla sottosequenza ottenuta dalla precedente, ignorandone l'ultima cella nel primo caso, la prima cella nel secondo caso.

Il termine bolle nel nome sta, infatti, ad indicare il procedimento per cui, ad ogni iterazione, gli elementi di peso maggiore si spostano verso il fondo della sequenza e quelli di peso minore verso la superficie della stessa.

Analizziamone più in dettaglio la strategia, attraverso un esempio grafico.

Supponiamo di dover ordinare gli elementi del vettore seguente in ordine crescente:

Sulla base dell'algoritmo descritto precedentemente, il vettore viene attraversato in una delle due direzioni, in questo caso dall'inizio verso la fine, confrontando le coppie di elementi adiacenti ed eventualmente scambiandoli di posto, se non ordinati secondo l'ordinamento voluto.
Si inizia pertanto confrontando i primi due elementi evidenziati.

In questo caso i due elementi sono nell'ordine giusto, per cui si procede con la coppia successiva

In questo caso i due elementi non sono nell'ordine giusto, pertanto si procede con lo scambio

Si continua poi, con procedimento analogo, con le coppie successive, fino a che si giunge alla fine del vettore.

Come si può notare, al termine di una iterazione, l'elemento maggiore del vettore è stato posizionato nella sua posizione corretta, ossia in fondo al vettore.
Gli elementi più piccoli, invece, si sono spostati di qualche posizione verso l'inizio del vettore.
A questo punto, si ripete il procedimento sulla sottosequenza del vettore costituita dai suoi elementi ad eccezione dell'ultimo.
Ad ogni iterazione si posiziona, pertanto, l'elemento maggiore in fondo alla sottosequenza, fino a quando essa non risulti costituita da un solo elemento.
Vediamo in che modo, quanto detto, si riflette nell'esempio considerato.

A questo punto termina la seconda iterazione.
Si può notare l'elemento 8 posizionato in fondo alla sottosequenza.
Si ripete considerando la sottosequenza costituita dagli elementi del vettore ad eccezione degli ultimi due.

Fine terza iterazione e nuova iterazione sulla sottosequenza dal primo al sesto elemento.

Fine quarta iterazione e nuova iterazione sulla sottosequenza dal primo al quinto elemento.

Fine quinta iterazione e nuova iterazione sulla sottosequenza dal primo al quarto elemento.

La versione dell'algoritmo descritta continuerebbe ad iterare fino a quando la sottosequenza non risulterà composta da un solo elemento, ordinata per definizione.
Tuttavia si può osservare che l'ultima iterazione non ha effettuato scambi tra gli elementi.
Questo ci porta a concludere che il vettore risulta già ordinato, per cui una ottimizzazione dell'algoritmo può arrestarsi anche alla prima iterazione che non effettua alcuno scambio.
Gli elementi del vettore, come si può vedere, risultano ordinati dal più piccolo al più grande.
Vediamone, a questo punto, una implementazione in linguaggio Java:

public static void bubbleSort(int[] v) {
    // la prima sequenza da esaminare
    // coincide con tutto il vettore
    int l = v.length;

    // esamino la sequenza fino a che essa
    // sia costituita da più di un elemento
    while (l > 1) {
        for (int j = 0; j < l - 1; j++) {
            // confronto gli elementi adiacenti
            // e li scambio nel caso in cui non
            // fossero nell'ordine corretto
            if (v[j] > v[j + 1]) {
                int t = v[j];
                v[j] = v[j + 1];
                v[j + 1] = t;
            }
        }
        // diminuisco la dimensione della 
        // sequenza da esaminare
        l--;
    }
}

L'implementazione appena vista non considera il caso in cui il processamento di una sequenza non effetti alcuno scambio, per cui essa continua fino a che la sequenza da esaminare non diventi di dimensione 1.

Di seguito riportiamo la versione ottimizzata dell'algoritmo, che termina le iterazioni anche nel caso in cui una sottosequenza non abbia alcun elemento da scambiare di posto, quindi sia già ordinata.

public static void bubbleSortOttimizzato(int[] v) {
    // la prima sequenza da esaminare
    // coincide con tutto il vettore
    int l = v.length;
    boolean scambio = true;

    // esamino la sequenza fino a che essa
    // sia costituita da più di un elemento
    // e nella precedente iterazione
    // ci sia stato almeno uno scambio
    while (l > 1 && scambio) {
        // suppongo che non ci saranno scambi
        scambio = false;
        for (int j = 0; j < l - 1; j++) {
            // confronto gli elementi adiacenti
            // e li scambio nel caso in cui non
            // fossero nell'ordine corretto
            if (v[j] > v[j + 1]) {
                int t = v[j];
                v[j] = v[j + 1];
                v[j + 1] = t;
                // segnalo lo scambio di elementi
                scambio = true;
            }
        }
        // diminuisco la dimensione della 
        // sequenza da esaminare
        l--;
    }
}

... non ancora disponibile

La strategia di ordinamento di questo algoritmo si basa sul principio divide et impera ed utilizza una logica ricorsiva.

Nel dettaglio, la sequenza iniziale viene scomposta in due sequenze più piccole, che vengono ordinate con la stessa logica e successivamente utilizzate per ricostruire la sequenza iniziale, questa volta ordinata, attraverso la fusione delle stesse.
Il principio divide et impera sostiene, infatti, che la scomposizione di un problema complesso in sottoproblemi di dimensione inferiore, ne semplifica la risoluzione.
Inoltre, abbiamo già visto, nella sezione degli esercizi, l'algoritmo per la fusione di due sequenze ordinate in un'unica sequenza ordinata.
Tale algoritmo non presenta delle particolari complessità.
Utilizzeremo, quindi, la tecnica della fusione per costruire sottosequenze ordinate del vettore iniziale, partendo da sottosequenze formate da un solo elemento (ordinate per definizione).

Procederemo poi a ritroso fondendo le sottosequenze ottenute, fino a ricostruire la sequenza originale con gli elementi ordinati. Approfondiamo attraverso un esempio grafico.
Supponiamo di dover ordinare gli elementi del vettore seguente in ordine crescente:

Sulla base dell'algoritmo descritto precedentemente, il vettore viene diviso in due metà e l'algoritmo viene richiamato su ciascuna metà, in modo ricorsivo, fino a giungere a delle sequenze di dimensione uno.

A questo punto le sequenze ordinate possono essere unite tra loro, utilizzando l'algoritmo della fusione, procedendo a ritroso, fino a giungere alla fusione delle due sequenze iniziali, in cui il vettore era stato diviso, che ricostruiranno il vettore iniziale ordinato.

public static void mergeSort(int[] v) {
        // chiamo la funzione ricorsiva, che contiene
        // i parametri per poter eseguire la ricorsione
        // e quindi determinare la sua terminazione
        mergeSortR(v, 0, v.length - 1);
    }

    // funzione ricorsiva
    public static void mergeSortR(int[] v, int iIn, int iFin) {
        // se l'indice iniziale non è minore di quello finale
        // vuol dire che la sequenza da ordinare è composta da 
        // uno o zero elementi, quindi è ordinata per definizione
        if (iIn < iFin) {
            // calcolo l'indice  mediano della sequenza
            int iMed = (iIn + iFin) / 2;
            // richiamo ricorsivamente la funzione 
            // sulle metà sinistra e destra
            mergeSortR(v, iIn, iMed);
            mergeSortR(v, iMed + 1, iFin);
            // alla fine eseguo la fusione delle 
            // due sequenze ordinate
            merge(v, iIn, iMed, iFin);
        }
    }

    public static void merge(int[] v, int iIn, int iMed, int iFin) {
        // effettua la fusione delle due sequenze
        // la prima con indice iniziale iIn e finale iMed
        // la seconda con indice iniziale iMed+1 e finale iFin
        // utilizzando un terzo vettore t che alla fine 
        // viene ricopiato nel vettore iniziale
        int iIn2 = iMed + 1;
        int l = iMed - iIn + 1 + iFin - iIn2 + 1;
        int i1so = iIn;
        int[] t = new int[l];
        for (int i = 0; i < l; i++) {
            if (iIn > iMed) {
                t[i] = v[iIn2];
                iIn2++;
            } else if (iIn2 > iFin) {
                t[i] = v[iIn];
                iIn++;
            } else if (v[iIn] < v[iIn2]) {
                t[i] = v[iIn];
                iIn++;
            } else if (v[iIn2] < v[iIn]) {
                t[i] = v[iIn2];
                iIn2++;
            } else {
                t[i] = v[iIn2];
                iIn2++;
                i++;
                t[i] = v[iIn];
                iIn++;
            }
        }
        
        // ricopio la sequenza ordinata
        // nel vettore iniziale
        for (int i = 0; i < l; i++) {
            if (v[i + i1so] != t[i]) {
                v[i + i1so] = t[i];
            }
        }
    }