Selection sort in Java

Il Selection Sort è un algoritmo di ordinamento decisamente semplice ed intuitivo. L’idea 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 nel vettore.

In altre parole, alla prima iterazione verrà selezionato il valore più piccolo dell’intero array e sarà scambiato con il valore che occupa la prima posizione. Alla seconda iterazione, il secondo valore più piccolo sarà scambiato con il valore in seconda posizione, e così via fino a quando tutti gli elementi del vettore non saranno collocati nella loro giusta posizione.

Implementazione dell’algoritmo Selection Sort in Java

Vediamo ora un’implementazione dell’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
            // aggiorniamo minimo all'elemento trovato
            if(array[minimo] > array[j]) {
                minimo = j;
            }
        }
        // Se minimo è diverso dall'elemento di partenza,
        // allora avviene lo scambio
        if(minimo != i) { 
            int k = array[minimo];
            array[minimo] = array[i];
            array[i] = k;
        }
    }
}

La complessità del Selection Sort risulta quadratica, sia nel caso peggiore, medio e migliore. Il numero di confronti è O(n²) in ogni caso. Mentre il numero di scambi è lineare O(n) nel caso peggiore e medio, ed è costante O(1) nel caso migliore. Questa caratteristica lo rende meno efficace su grandi dataset rispetto ad altri algoritmi di ordinamento come Quick Sort o Merge Sort.

Considerazioni e Vantaggi del Selection Sort

Nonostante la sua semplicità, il Selection Sort presenta alcuni vantaggi:

• È facile da capire e implementare.
• Non richiede memoria ausiliaria, in quanto funziona in-place.
• È utile per data set di dimensioni ridotte.
• È stabile in alcune implementazioni, a seconda della gestione degli scambi.

Tuttavia, per dataset più grandi e per applicazioni che richiedono efficienza, è consigliabile considerare algoritmi più performanti, come il Merge Sort o il Quick Sort, che hanno una complessità media di O(n log n).