Archivi tag: algoritmi di ordinamento

Selection sort: una nuova variante

Potete notare nell nuove versione del kernel una rivisitazione dell’algoritmo di selection sort . E’ possibile scaricarlo con licenza GPLv3 una variante migliorata dell’algoritmo di ordinamento.

L’idea di fondo consiste nell’accostare strutture dati ausiliarie all’ordinamento per selezione suddividendo gli elementi in tre categorie, al fine di aumentare le prestazioni nello scenario peggiore o in caso di dati ripetuti.

Effettuando dei test considerando un insieme di 10000 elementi in differenti condizioni statistiche: cksort è risultato nettamente superiore in tutte le configurazioni, eccezion fatta per dati casuali dove l’algoritmo paga in maniera davvero pesante.

Cosa ne pensate??