Informatica I - ordinamento per selezione

Algoritmi per ordinare un insieme di numeri

Analizziamo gli algoritmi per ordinare un insieme di numeri (interi) memorizzato in un array. Prendiamo in esame un array a da ordinare in senso crescente.

Passaggi per ordinare un array

• Per prima cosa, bisogna trovare l’elemento dell’array contenente il valore minimo (in a[3]), questo caso è il numero 5 in posizione a[0].
• Essendo l’elemento minore, la sua posizione corretta nell’array ordinato è a[0].
• In a[0] è memorizzato il numero 11, da spostare. Non sappiamo quale sia la posizione corretta di 11 ma lo spostiamo temporaneamente in a[3].
• Scambiamo a[0] con a[3]. La parte sinistra dell’array è già ordinata e non sarà più considerata.
• Ordiniamo la parte destra con lo stesso algoritmo: cerchiamo l’elemento contenente il valore minimo, che è il numero 9 in posizione a[1].
• Dato che è già nella prima posizione della parte da ordinare (a[1]), non c’è bisogno di fare scambi.
• Ordiniamo il resto dell’array con lo stesso algoritmo. Ad un certo punto la parte da ordinare contiene un solo elemento, quindi è ovviamente ordinata.

Implementazione della classe ArrayAlgs

Scriviamo la classe ArrayAlgs che conterrà le realizzazioni dei vari algoritmi di ordinamento e ricerca da noi studiati.

Esempio di codice: Selection Sort

public static void selectionSort(int[] v, int vSize) {
    for (int i = 0; i < vSize - 1; i++) {
        int minPos = findMinPos(v, i, vSize-1);
        if (minPos != i) swap(v, minPos, i);
    }
}

// abbiamo usato due metodi ausiliari, swap e findMinPos
private static void swap(int[] v, int i, int j) {
    int temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

private static int findMinPos(int[] v, int from, int to) {
    int pos = from;
    int min = v[from];
    for (int i = from + 1; i <= to; i++) {
        if (v[i] < min) {
            pos = i;
            min = v[i];
        }
    }
    return pos;
}