Abstrait

Ingénierie d'un algorithme de partitionnement Quicksort

D. Abhyankar et M. Ingle

L'un des algorithmes de tri les plus sophistiqués de la littérature sur le tri est Quicksort. Bien que Quicksort présente plusieurs aspects frappants, la conception de la fonction de partition est l'aspect central de l'algorithme Quicksort. Le partitionnement est un domaine méticuleusement étudié dans lequel nous trouvons la partition Hoare et la partition Lomuto comme deux algorithmes de partition importants dans la littérature. Malgré le fait que beaucoup d'efforts ont été concentrés sur la recherche sur le partitionnement, il semble que le partitionnement soit encore insuffisamment compris et se prête à un bon mélange d'optimisations. Des algorithmes de partitionnement supérieurs peuvent être conçus en utilisant un mélange parfait de mesures d'amélioration des performances et une touche d'élégance. Cet article postule deux nouveaux algorithmes de partition qui sont meilleurs que ceux existants. L'algorithme proposé3 applique des optimisations efficaces et, de ce fait, le nombre d'instructions est réduit. Le nombre réduit d'instructions aide la fonction à obtenir des performances spectaculaires. L'algorithme présenté4 est un algorithme élégant, compact et intensément compétitif du point de vue des performances.