Selection sort in Java

Il Selection Sort è un altro algoritmo di ordinamento decisamente semplice ed intuitivo. L’ dea di base si fonda nel selezionare ad ogni iterazione l’i-esimo valore piú piccolo, e sostituirlo con quello che, in quel momento, occupa l’ i-esima posizione.

In altre parole alla prima iterazione verrá selezionato il valore piú piccolo dell’intero vettore e sará scambiato con il valore che in quel momento occupa la prima posizione, poi alla seconda iterazione viene selezionato il secondo valore piú piccolo del vettore e sará scambiato con il valore che in quel momento occupa la seconda posizione, e cosí via fino a quando tutti gli elementi del vettore non sono collocati nella loro giusta posizione.

Vediamo l’implementazione algoritmo Selection Sort in Java:

public void selectionSort(int [] array) {
    for(int i = 0; i < array.length-1; i++) {
        int minimo = i; //Partiamo dall' i-esimo elemento
        for(int j = i+1; j < array.length; j++) {
        //Qui avviene la selezione, ogni volta
        //che nell' iterazione troviamo un elemento piú piccolo di minimo
        //facciamo puntare minimo all' elemento trovato
            if(array[minimo]>array[j]) {
                minimo = j;
            }
        }
        //Se minimo e diverso dall' elemento di partenza
        //allora avviene lo scambio
        if(minimo!=i) { 
            int k = array[minimo];
            array[minimo]= array[i];
            array[i] = k;
        }
    }
}

In questo caso la complessitá risulta quadratica sia nel caso peggiore, medio e migliore.Il numero di confronti é O(n^2) in ogni caso. Mentre il numero di scambi è lineare O(n) nel caso peggiore e medio, mentre é costante O(1) nel caso migliore.