Follow

Rappresentazione grafica di un ordinamento con Selection Sort

Nell’ultimo appuntamento abbiamo visto e analizzato gli aspetti generali dell’Insertion Sort e notato che esso non è affatto un algoritmo usabile in pratica per istanze (ovvero input) molto grandi.

Ovviamente l’Insertion Sort non è l’unico algoritmo di sorting esistente. Nella nostra ricerca dell’algoritmo ottimo di sorting oggi guarderemo il Selection Sort.

for i = 0 to n-2 :
    min = i
    for j = (i + 1) to n-1 :
        if A[j] < A[min] :
            min = j
    swap A[i] and A[min]

Il principio su cui si basa il Selection Sort è veramente molto semplice. In pratica dato un array A, seleziona il minimo e lo mette in testa, poi, nel sotto-array di dimensione n-1 seleziona il minimo e lo mette in seconda posizione… e cosi via. Vediamolo con un esempio.

8i 4 5 6 2 3 min=2
2 4i 5 6 8 3 min=3
2 3 5i 6 8 4 min=4
2 3 4 6i 8 5 min=5
2 3 4 5 8i 6 min=6
2 3 4 5 6 8 (finito)

Il problema di questo algoritmo è che la ricerca del minimo in un passo non da alcuna informazione su quale sia il minimo nel passo successivo. Per questo motivo ad ogni passo, indipendentemente dall’ordinamento dell’input, dobbiamo effettuare la suddetta ricerca. Quindi, poiché la ricerca del minimo ha costo lineare, al primoi passo dovremo pagare n, poi n-1, poi n-2, finché non avremo ordinato tutto l’array.

Ovvero n  + (n-1) + (n -2) + … + 1 e quindi, parimenti all’Insertion Sort, la complessità sarà di O(n²)! Con la differenza che il Selection Sort rimane quadratico anche per un input già ordinato.

Data la quadraticità dell’algoritmo possiamo effettuare integralmente le stesse considerazioni di “tempo di calcolo” che facevamo con l’Insertion Sort.

Anche il selection sort quindi è un algoritmo molto sconveniente. La nostra ricerca deve quindi proseguire.