Con Kolivas, grazie al supporto grafico fornito da Sorting-Algorithms, ha ripensato il vecchio approccio a tre bucket di cksort. Per bucket si intende un contenitore di oggetti della stessa categoria: la vecchia versione prevedeva che il primo bucket contenesse il primo oggetto e tutti gli oggetti maggiori o uguali all’ultimo inserito. Il secondo contenitore era deputato a raccogliere le istanze scartate dal primo più tutte quelle uguali o minori, per poi depositare gli elementi non ordinati nel terzo contenitore.
Con la nuova versione, cksort risulta essere più veloce del quicksort con insiemi fino a 1500 elementi. Il problema maggiore della vecchia versione era l’estrema lentezza nell’ordinare interi generati con una distribuzione puramente casuale. La nuova concezione del metodo a tre bucket utilizza il primo ed il terzo non più come la parte da ordinare ma come «pre-passaggio». Le modifiche apportate hanno dato frutti per tutte le configurazioni migliorando di 20 volte le prestazioni in caso di dati casuali non ripetuti.
Per chi vuole approfondire l’algoritmo è possibile vederlo in azione con una visualizzazione grafica con dati casuali, parzialmente ordinati, e dati ripetuti. Sarà interessante vedere applicazioni nel mondo reale di questo «esercizio intellettuale».
Via | ck Hacking
Con Kolivas migliora il suo algoritmo derivato dal selection sort é stato pubblicato su Ossblog.it alle 10:00 di domenica 09 ottobre 2011.