Selection Sort

Algoritmo intuitivo e più veloce del bubble sort.

Si può individuare il valore minimo in un array V e scambiarlo con il valore alla prima posizione.

In questo modo l’elemento alla posizione 1 occupa definitivamente il posto che gli spetta…

Ripetendo la stessa operazione con i sottovettori

da 2 a N-1
da 3 a N-1

da N-1 a N

andranno al loro posto gli elementi alla posizione 2, 3, …, N-1.
L’elemento alla posizione N occuperà l’unico posto rimasto libero per l’elemento più grande…

Osserva

ss1

Miglioramento

Con un If(...) Then... aggiuntivo si può evitare di eseguire inutilmente la SCAMBIA() quando un elemento occupa già il posto giusto

Complessità dell’algoritmo

Quanti sono i controlli e le esecuzioni di SCAMBIA()?

i j TC TS
1 2…n n-1 1
2 3…n n-2 1
n-1 n 1 1

Calcolo di TC(n)

TC(n)=(n-1)+(n-2)+...+1

Quanto vale la somma?

T(n)=(n-1)n/2 = ½n2-½n.

La complessità in tempo asintotica dell’algoritmo di ordinamento selection sort è O(n2), per il numero di confronti.

Il numero di scambi è

TS(n)=1+...+1=n-1

La complessità in tempo asintotica dell’algoritmo di ordinamento selection sort è O(n), per il numero di scambi.