Informatica I - ordinamento per inserimento InsertionSort

Algoritmo di ordinamento per inserimento

L’algoritmo di ordinamento per inserimento inizia osservando che il sottoarray di lunghezza unitaria costituito dalla prima cella dell’array è ordinato (essendo di lunghezza unitaria). Estende verso destra la parte ordinata, includendo nel sottoarray ordinato il primo elemento alla sua destra. Per farlo, il nuovo elemento viene spostato verso sinistra finché non si trova nella sua posizione corretta, spostando verso destra gli elementi intermedi.

Il codice dell’algoritmo è il seguente:

public class ArrayAlgs {
    ...
    public static void insertionSort(int[] v, int vSize) {
        // Il ciclo inizia da 1 perché il primo elemento non richiede attenzione
        for (int i = 1; i < vSize; i++) {
            int temp = v[i]; // nuovo elemento da inserire
            // j va definita fuori dal ciclo perché il suo valore finale viene usato in seguito
            int j;
            // Sposta di uno verso destra tutti gli elementi a sinistra di temp e > di temp partendo da destra
            for (j = i; j > 0 && temp < v[j-1]; j--) 
                v[j] = v[j-1];
            v[j] = temp; // inserisci temp
        }
    }
    ...
}