Ho preparato un PDF con la dimostrazione del lower bound per algoritmi di ordinamento. Può contenere ancora qualche svista ma dovrebbe essere piuttosto corretto e fornire, a chi vuole, una dimostrazione semplificata del perché non può esistere un algoritmo di ordinamento con complessità inferiore a O(n log(n)).
L'algoritmo di Bubble Sorting in azione.
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 o i volumi di un agrande biblioteca.
Dobbiamo proseguire la nostra ricerca, cambiamo approccio, questa volta il nostro tentativo cade sul Bubble Sort.
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.
Continue reading »
Come ordina l'insertion sort.
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. Continue reading »
Recent Comments