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.
Ripetete per tutte le carte finchè non le avete tutte in mano ed ordinate.

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

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

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.

Pseudocodice del Selection Sort

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

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

Esempio di implementazione in Python3

Ecco un esempio di implementazione del Selection Sort in Python, che cerca di seguire il più possibile lo schema dello pseudocodice proposto sopra:

def selectionSort(arr):
    for j in range(0, len(arr)-1):
        posmin = j
        for i in range (j+1, len(arr)):
            if(arr[i] < arr[posmin]):
                posmin = i
        aus = arr[j]
        arr[j] = arr[posmin]
        arr[posmin] = aus
    return arr

import unittest
import random

class SortingTest(unittest.TestCase):
    def setUp(self):
        self.i = list(range(0, 100))
        self.sort = selectionSort

    def testOrdered(self):
        self.assertEqual(self.i, self.sort(self.i))

    def testReversed(self):
        self.assertEqual(self.i, self.sort(self.i[::-1]))

    def testUnordered(self):
        self.assertEquals(self.i, self.sort(random.sample(self.i, len(self.i))))

if __name__ == "__main__":
    unittest.main()