ordinamento

Molto spesso dato un elenco di informazioni serve metterlo in ordine (ad esempio perché cercare un elemento su un elenco ordinato è molto più facile che in uno non ordinato), se si tratta di numeri dal più piccolo al più grande (o viceversa), se si tratta di parole in ordine alfabetico o altro ordinamento per altri tipi di oggetti.

Potrebbe essere sorprendente ma esistono molte soluzioni per mettere in ordine gli elementi di un vettore, alcune sono più veloci, altre meno, alcune usano più memoria, altre meno...

Bubble Sort

L'idea è quella di portare a galla gli elementi più leggeri.

Poniamo che a sia il vettore di interi da ordinare: l'agoritmo inizia confrontando gli ultimi due elementi, se l'ultimo è più piccolo del penultimo li scambia poi procede spostandosi verso l'alto e applicando il procedimento al terzultimo e il penultimo e così via fino ad arrivare a quelli ai primi due posti. A questo punto avremo in posizione zero l'elemento più piccolo.

Procedendo alla stessa maniera (ma fermandomi al posto uno anziché al posto zero perché nel posto zero sappiamo già esserci l'elemento più piccolo) "porto a galla" il secondo elemento. Via di seguito facciamo la stessa cosa ogni volta fermandoci una posizione prima.

In pseudocodice:

for(superficie=primo;superficie<=ultimo-1;superficie=superficie+1){
  for(posizione=ultimo-1;posizione>=superficie;posizione--){
    if(v[posizione]>v[posizione+1]){
      appoggio=v[posizione];
      v[posizione]=v[posizione+1];
      v[posizione+1]=appoggio;
    }
  }
}
	

Merge sort

L'idea di partenza è che avendo due vettori già ordinati fonderli in un unico vettore ordinato è una cosa facile: basta guardare l'elemento di testa di ogni vettore e decidere se prendere l'uno o l'altro, una volta preso lo togo e torno a fare la stessa operazione sugli elementi che restano.

Proviamo a limitarci alla parte gialla del giagramma qui sotto. Devo fondere i vettori [3,8] e [1,5]. Guardo gli elementi di testa "3" e "1" e prendo uno, successivamente guardo gli elementi che restano in cima cioè "3" e "5" e prendo 3, continuo così finche non fininscono tutti gli elementi.

Qui sotto è riportato il codice che implementa l'algoritmo, per utilizzarlo va chiamato il metodo mergeSort() passando come parametro il vettore da ordinare.

public class Sort {

    public static void mergeSort(int[] vettore) {
        ordina (vettore, 0, vettore.length-1);
    }

    /************************************************************************
     * Funzione che implementa l'algoritmo Merge Sort,
     * divide (soltanto dal punto di vista logico) il vettore in due parti
     * le ordina e poi le fonde 
     * @param v      il vettore da ordinare
     * @param primo  il primo elemento da ordinare del vettore (es: 0)
     * @param ultimo l'ultimo elemento da ordinare del vettore (es: v.length-1)
     ***********************************************************************/
    public static void ordina(int[] v, int primo, int ultimo){
        int medio;
        if(primo<ultimo){
            medio=(ultimo+primo)/2;
            ordina(v,primo,medio);
            ordina(v,medio+1,ultimo);
            merge(v,primo,ultimo,medio);
        }
    }
 
    /************************************************************************
     * Fonde due semi-vettori, 
     * il primo va da "primo" a "medio"
     * il secondo da "medio+1" a "ultimo"
     * @param v     vettore che contiene le due parti da fondere
     * @param primo primo elemento del primo semi-vettore
     * @param ultimo    ultimo elemento del secondo semi-vettore
     * @param medio ultimo elemento del primo semi-vettore
     ***********************************************************************/
    private static void merge(int[] v, int primo, int ultimo, int medio){
        int appoggio[] = new int [ultimo-primo+1];
        int inserimento=0;
        int indicePrimo=primo;
        int indiceSecondo=medio+1;
        int i;
        
        // fondo la parte iniziale dei due vettori
        while(indicePrimo<=medio && indiceSecondo<=ultimo){
            if(v[indicePrimo]<v[indiceSecondo]){
                appoggio[inserimento]=v[indicePrimo];
                indicePrimo=indicePrimo+1;
            }else{
                appoggio[inserimento]=v[indiceSecondo];
                indiceSecondo=indiceSecondo+1;
            }
            inserimento=inserimento+1;
        }
        // a questo punto potrebbe essere restata una parte del primo o del secondo pezzo
        // ma non di entrambe
        if(indicePrimo<=medio){
            // bisogna finire di inserire il primo vettore
            for(i=indicePrimo;i<=medio;i=i+1){
                appoggio[inserimento]=v[i];
                inserimento=inserimento+1;
            }
        }else{
            // bisogna finire di inserire il secondo vettore
            for(i=indiceSecondo;i<=ultimo;i=i+1){
                appoggio[inserimento]=v[i];
                inserimento=inserimento+1;
            }
        }
        // copio il vettore di appoggio nel vettore originale
        for(i=0;i<appoggio.length;i=i+1){
            v[primo+i]=appoggio[i];
        }
    }
}

Confronto

Perché mai usare MergeSort che è così complicato quando BubbleSort funziona e è tanto semplice?

Perché MergeSort è molto, molto, molto più veloce di BubbleSort! Ad esempio su un i7 a 2.5GH per ordinare 1000 nomi Merge impiega 1msec mentre Bubble 21msec... sembra una differenza trascurabile ma vediamo qualche caso reale: l'anagrafe di un comune vuole creare un elenco di cittadini ordinati per nome, cosa succederebbe in comuni di diverse dimensioni?

Senza addentrarci nella spiegazione formale (che esiste, basta cercare "calcolo della complessità") sul perché Merge è più veloce di Bubble in questo contesto ci basta notare che scrivere un programma in modi diversi cambia di molto la sua velocità di esecuzione.