Erreur algo quick sort ?

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 :

http://guigouz.free.fr/quicksort.jpg

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

Fia,

Plutôt qu'un joli dessin, ton code serait nettement plus utile. :)

A priori, l'algo exposé est bon... et pas du tout adapté au tri de listes chaînées. C'est un quicksort en place sur un tableau ça, si tu le suis à la lettre, tu vas te retrouver avec du O(n^3)... :aie:

Quant à ton problème, c'est sans doute une erreur dans ta retranscription de l'algorithme.

--
Jedaï

Voici le code !

Fonction triQuickSort :

Code:

---

1 2 3 4 5 6 7 8 9 10

void triQuickSort(String^ pChamp, String^ pOrdre, int d, int f) { int milieu; if(d < f) { milieu = partition(pChamp, pOrdre, d, f); triQuickSort(pChamp, pOrdre, d, milieu-1); triQuickSort(pChamp, pOrdre, milieu+1, f); } }

---

Fonction partition :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

int partition(String^ pChamp, String^ pOrdre, int d, int f) { cellule<T> ^maCellulePivot = renvoyerCellule(f); T ^monPivot = maCellulePivot->getElement();   cellule<T> ^maCelluleJ; cellule<T> ^maCelluleI; T ^monElementTmp;   int i = d-1; for(int j(d); j < f; j++) { maCelluleJ = renvoyerCellule(j); monElementTmp = maCelluleJ->getElement();   if ( (monPivot->comparer(pChamp, monElementTmp, monPivot)) ) { if ( pOrdre == "asc" ) { i++; maCelluleI = renvoyerCellule(i);   intervertir(maCelluleI, maCelluleJ); } } else { if(pOrdre == "desc") { i++; maCelluleI = renvoyerCellule(i);   intervertir(maCelluleI, maCelluleJ); } } } i++; maCelluleI = renvoyerCellule(i); intervertir(maCelluleI , maCellulePivot); return i; }

---

Merci de t'intéresser à mon problème !!
La liste chainée du code ci-dessus est une classe template qui contient des cellules. La cellule est une classe template qui contient un objet (ici appelé element)...

Rapidement (parce que je ne vois en quoi c'est codé), il me semble que tu oublies de trier l'élément milieu :

triQuickSort(pChamp, pOrdre, d, milieu-1);
triQuickSort(pChamp, pOrdre, milieu+1, f);

Il y a peut être d'autres choses. As-tu le même comportement avec un tableau plus grand ?

Nil

Bonsoir

En fait c'est ma fonction intervertir qui pose soucis (plus quelques autres détails corrigés). J'ai recodé tout ce bazar avec un simple tableau pour tester et effectivement l'algo est bon (très bon même !). En suivant les mouvements des valeurs dans les deux cas, j'ai compris que la fonction intervertir n'était pas vraiment opérationnelle !!

Je viens de me rendre compte à quel point il peut être complexe d'échanger la place de deux éléments dans une liste... y'a des pointeurs dans tous les sens et je ne suis pas encore très habitué ! Cela dit c'est une excellente auto-formation ! Si j'y arrive sa va être bien pour les exams de fin d'année !

Merci à tous ceux qui m'ont répondu et désolé d'avoir douté de l'algo de celui qui a plein d'étoiles et de plumes ! :D

PS : Jedi peux-tu me dire pourquoi cet algo n'est pas adapté aux listes chainées ? Au final je ne fais que comparer des chaines ou des entiers afin remettre les cellules de ma liste dans le bon ordre. As-tu un meilleur tri le cas échéant ? Par insertion ? :?

Bonsoir bonsoir
Guigouz

Citation:

---

Envoyé par guigouz

PS : Jedi peux-tu me dire pourquoi cet algo n'est pas adapté aux listes chainées ? Au final je ne fais que comparer des chaines ou des entiers afin remettre les cellules de ma liste dans le bon ordre. As-tu un meilleur tri le cas échéant ? Par insertion ? :?

---

Réfléchis au coût des opérations que tu utilises à chaque étape ! intervertir() par exemple est en O(n). Sur un tableau toutes ces opérations seraient en O(1), mais sur une liste chaînée ce n'est pas le cas du tout... :aie:

On peut tout à fait utiliser le quicksort sur des listes chaînées, en fait l'un des exemples classiques en Haskell (langage fonctionnel, où les listes chaînées sont très communes) est le quicksort suivant :

Code:

---

1 2 3

quicksort [] = [] quicksort (x:xs) = quicksort ltx ++ [x] ++ quicksort gex where (ltx, gex) = partition (< x) xs

---

( (x : xs) est la liste de premier élément xs et de queue xs, (++) concatène deux listes et (partition prédicat xs) découpe la liste xs en deux listes : éléments pour lesquels le prédicat est vrai et éléments pour lesquels le prédicat est faux, [] est la liste vide)

Il faut simplement faire ça différemment bien qu'en gardant la même idée : pour une liste contenant l'élément x, si on concatène la liste triée contenant les éléments inférieur à x, la liste contenant seulement x et la liste triée contenant les éléments supérieur à x, alors on obtient la liste originale triée.

Un autre tri populaire pour les listes chaînées (et plus rarement utilisé sur les tableaux) est le tri fusion, qui a pas mal d'avantage sur le tri rapide dans le cas des listes chaînées.

--
Jedaï