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