L’algoritmo Selection Sort è quello più semplice, quello che seguirebbe istintivamente qualsiasi persona. Da un gruppo da ordinare seleziona il più piccolo, lo toglie, e lo inserisce nella giusta posizione in un gruppo ordinato.
In termini un po’ più tecnici, l’algoritmo ripete per n volte una procedura in grado di selezionare alla i-esima iterazione l’elemento più piccolo nell’insieme e di scambiarlo con l’elemento che in quel momento occupa la posizione i.
Ossia, alla prima iterazione verrà selezionato l’elemento più piccolo dell’intero insieme e sarà scambiato con quello che occupa la prima posizione; alla seconda iterazione sarà selezionato il secondo elemento più piccolo dell’insieme ridotto (cioè costituito dagli elementi {a2,a3,…,an} ) e sarà scambiato con l’elemento che occupa la seconda posizione, e così via fino ad aver collocato nella posizione corretta tutti gli n elementi.
Considerando un vettore di n elementi l’algoritmo può essere codificato nel seguente modo :
per i = 1, 2,...,n ripeti per j = i +1,...,n ripeti se aj < ai allora scambia ai e aj fine-condizione fine-ciclo fine-ciclo
In java diventa:
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;
}
}
}
Esempio
Supponiamo di applicare il selection sort al seguente array
A = {4, 2, 1, 3}
Ad ognuno dei passi dell’algoritmo, viene selezionato l’elemento più piccolo nella porzione di insieme ancora da ordinare, scambiandolo con l’elemento che si trova nella prima posizione di tale sottoinsieme.
i = 1 A = (4, 2,1, 3) → A = (1 | 2, 4, 3)
i = 2 A = (1 | 2, 4, 3) → A = (1, 2 | 4, 3)
i = 3 A = (1, 2, | 4,3) → A = (1, 2, 3 | 4)
i = 4 A = (1, 2, 3 | 4) → A = (1, 2, 3, 4)
Dopo 4 iterazioni, l’array sarà ordinato.
Per misurare le prestazioni dell’algoritmo (anche detta complessità) conteremo il numero di confronti.
Alla prima ripetizione del ciclo esterno vengono compiute n −1 operazioni con il ciclo interno; alla seconda ripetizione del ciclo esterno vengono eseguite n−2 operazioni con il ciclo interno, e così via fino a quando i = n.
Il numero di confronti totali sarà:
(N-1) + (N-2) + (N-3) + … + 2 + 1 = N*(N-1)/2 = O(N2)
Da notare che l’algoritmo fa gli stessi confronti sia per un array disordinato, sia per un array già ordinato, ossia per il selection sort non esiste un caso migliore o peggiore ma fa sempre tutti i confronti.
Viene usato quando l’insieme da ordinare è composto da pochi elementi e quindi, anche se non è molto efficiente, ha il vantaggio di non essere troppo difficile da implementare.