messa a punto di algoritmi di ordinamento: quicksort e timsort

Il problema dell'ordinamento ha una soluzione computazionalmente ottima in tempo O(n log(n)). Vi sono diversi algoritmi ottimali come Mergesort e Timsort, ma anche alcuni algoritmi non ottimali nel caso peggiore sono di fatto molto efficienti in pratica, come per esempio Quicksort che, non solo esibisce un tempo medio O(n log(n)) in ipotesi di distribuzione uniforme dei dati, ma è anche davvero efficiente in molte implementazioni. Nel primo capitolo vengono definiti i vari algoritmi di ordinamento che verranno utilizzati nel corso della stesura della tesi, analizzandone in particolare il costo computazionale. I primi algoritmi ad essere esposti sono Insertion sort e Binary insertion sort, seguiti poi dagli algoritmi basati sulla tecnica "Divide et Impera": Mergesort, Quicksort e Timsort. Nel secondo capitolo la tesi presenta alcune "messe a punto" di Quicksort, cioè euristiche che ibridano l'algoritmo originale con altri algoritmi, non ottimali nel caso peggiore, ma che combinati con Quicksort possono migliorare la sua già buona performance. In particolare viene prima confrontato Quicksort con gli algoritmi Insertion sort e Binary insertion sort per liste di dimensioni limitate, per poi modificarne l'algoritmo utilizzando diverse lunghezze per l'applicazione di Insertion sort su di esso, ottenendo sperimentalmente la combinazione più efficiente. Nel terzo capitolo vengono infine confrontati gli algoritmi più efficienti: Quicksort ottimizzato ottenuto nel capitolo precedente con due diverse versioni di Timsort, una più "semplice" enunciata nel primo capitolo ed una più fedele all'originale. Il confronto viene in primis sviluppato sul caso di lista generata casualmente, ma vengono prese in considerazione anche casistiche particolari, come ad esempio in presenza di liste già ordinate.