Insertion Sort e Selection Sort non si sono rivelati all’altezza delle nostre aspettative e noi ci ritroviamo ancora senza un algoritmo efficente per ordinare, o meglio: sappiamo ordinare le tracce di un album, oppure i CD di un apiccola collezione domestica, ma avremo molte difficoltà nell’ordinare in ordine di età gli abitanti di Roma …

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 …

Volevo discutere in qualche articolo alcuni problemi di algoritmica presentando alcuni algoritmi che li risolvono e analizzandone la complessità.

Cominciamo questa vetrina di algoritmi con quelli che risolvono il più classico dei problemi: l’ordinamento.

In particolare cominceremo vedendo uno dei più semplici: insertion sort.Insertion Sort :
def insertion_sort(x, n) :
for i = 1 …