Selection Sort: un’ algoritmo per ordinare

Algo1 Icon

Selection Sort: un’ algoritmo per ordinare

0

Uno delle aree principali dello studio di algoritmi, si basa sul trovare il modo migliore per ordinare un insieme di oggetti.

Abbiamo già visto l’ Insertion Sort, ed oggi ne vedremo uno simile: il Selection Sort.

Nell’ altro articolo, per spiegare il funzionamento dell’algoritmo, ho utilizzato come esempio l‘ordinamento di una mano a carte. Vorrei modificare l’esempio in modo da farvi capire facilmente come funziona questo algoritmo:

Avete le carte scoperte sul tavolo. Cercate la più piccola e la tenete in mano. Cercate un’altra carta, sempre la più piccola, e prendetela in mano, mettendola a destra della carta che avete in mano. Cercate nuovamente la carta più piccola, e affiancatela a destra delle altre due che saranno sicuramente più piccole. Eccetera.

Diciamo che non è sicuramente il modo più intuitivo per ordinare una mano di carte: il nome Selection sort, ordinamento per selezione, ci fà capire subito il riferimento alla scelta del minimo ad ogni ciclo.

Questo algoritmo, come l’ insertion sort, è molto inefficiente: in tutti i casi alla peggio andrà come O(n2).

Ordina “In place” in quanto non ha bisogno di nessun array di supporto e la sua velocità dipende dalla dimensione dell’ input: potrebbe quindi essere conveniente usarlo per array di piccole dimensione.

Essendo comunque anche questo, come l’ Insertion Sort, abbastanza facile da implementare per piccolo array potrebbe tornarci utile.

2 4 1 3 6 5

Pseudocodice del Selection Sort

Ecco quindi lo pseudocodice del Selection Sort: potete tranquillamente rimplementarlo in qualunque linguaggio  vogliate.

for j=1 to array.length-1: //Scorro l' array per la lunghezza
	posmin = 1 //Imposto l'indice della posizione minima
	for i=(j+1) to array.length: //Cerco il minimo
		if(array[i] < array[posmin])
			posmin = i;
	aus= a[j]
	a[j] = a[posmin]
	a[posmin] = aus

Come si può notare, essendo per altro un codice iterativo, il Selections Sort è facilmente implementabile in praticamente tutti i linguaggi di programmazione in quanto poi non richiede che un array come struttura dati.

About the Author

Federico PonziStudente, Webmaster ed appassionato di tutto ciò che è informatico con una spruzzata di scienza.View all posts by Federico Ponzi

Leave a Reply