Selection Sort

Il Selection Sort è un altro 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.

In altre parole alla prima iterazione verrá selezionato il valore piú piccolo dell' intero vettore e sará scambiato con il vaolore 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' algoritmo :
    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.

Questa é l' applet che ci mostra l' esecuzione del Selection Sort :

Per potere utilizzare questo tool necessaria l' installazione della Java Virtual Machine.
Scarica la Java Virtual Machine

Inserite manualmente i numeri nelle caselle, oppure usate la generazione automatica, con gli opportuni pulsanti : Random (casuale), Crescente e Descrescenti. Per far partire l' ordinamente usate il pulsante Ordina e regolate la velocita con l' apposita slider.