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).
