lundi 4 mai 2015

Oyelami's Sort

En me documentant sur les algorithmes de tri, je suis tombé sur ce papier (en anglais) du professeur Oyelami Olufemi Moses, de la Covenant University, au Nigéria.

Comme j'ai rarement l'occasion de voir des publications d'universitaires africains (d'habitude je lis surtout des articles d'universitaires américains ou européens) je me suis précipité dessus. Et comme en plus le professeur Oyelami Olufemi y décrit une nouvelle variante du tri bulle, cela m'intéressait encore plus.

L'idée d'Oyelami est d'ajouter une phase de préparation à un classique tri cocktail. Durant cette phase, on compare le premier et le dernier élément de la liste à trier et on les permute si nécessaire. Puis on continue avec le second et l'avant-dernier. Puis le troisième et l'antépénultième... A la fin de cette phase, on embraye sur un tri cocktail.

Cette amélioration va, certes, permettre aux petits éléments qui se trouvent en fin de liste de migrer plus rapidement vers le début. De même, une liste triée en ordre inverse sera triée en une seule passe. Mais en dehors de ce cas, les performances de ce tri restent bien loin de celles du tri à peigne.



Donc, à l'arrivée, je suis plutôt déçu. Vous pourrez voir le détail de ce tri ici.




Aucun commentaire:

Publier un commentaire