Selection Sort

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.

(Visited 15 times, 1 visits today)

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *