Bonjour,
Je suis en train de réaliser un programme sur une liste chaînée que l'on peut trier. J'ai tenté de mettre en oeuvre l'algo proposé sur developpez (Quick Sort) http://algo.developpez.com/sources/?page=tri#tri_rapide
Après avoir remarqué que cela ne marchait pas (chez moi), j'ai voulu faire tourner cet algo pour voir à quel moment mon code ne faisait plus la même chose.
Prenons quatre éléments A B C D (dans cet ordre) que l'on cherche à trier de manière décroissante (on cherche donc à obtenir D C B A). L'image ci-dessous permet de visualiser l'appel de la fonction Partition et ses opérations les trois premières fois :
On constate étrangement que lors des trois premiers passages, la fonction échange de place toujours les mêmes éléments... Si je continue à la faire tourner, elle n'échange jamais deux éléments différents... et le tri n'est pas du tout réalisé !
A mon avis l'algo est bon puisqu'il est la depuis deux ans et que je suis dessus depuis deux jours (surtout que celui qui l'a posé a plein d'étoiles !!).
Mais si quelqu'un voyait en quoi ce qui est au-dessus à un sens je pourrais peut-être avancer !
Merci d'avance ! Bonsoir...
Guigouz
Partager