Quicksort récursif, condition d'arrêt le probleme ?

Bonjour,

Dans le cadre d'un projet d'informatique sur les algorithmes génétiques, j'ai du faire une fonction Quicksort, elle marche mais le problème c'est quand la population a un trop grand nombre d'individus, là ca rame énormément et après le processus s'arrête sans arriver à terme et je ne trouve pas d'ou vient le probleme.
Je sais que sans tout le reste du projet, c'est difficile de pouvoir m'aider mais peut-etre qu'en jetant un oeil a ma fonction Quicksort, vous pourriez voire un petit problème de la gestion de la mémoire ou quelque chose du genre qui ferait que j'ai un problème quand le nombre devient trop important... à moins que le problème n'est pas vraiment la taille de la liste mais peut-être un autre problème vu que si la liste est plus grande, il y a plus de chances d'avoir une valeur qui ne fonctionne pas avec ma fonction... Je pencherais meme plus pour ca vu que j'ai essayé plusieurs fois avec une meme taille et un coup ca avait passé nickel... 8O

Merci
Bonne après-midi..


Je pense avoir localisé le problème, j'ai placé un printf("b"); dans le dernier else (ou on rappelle la fonction récursivement) et j'ai observé que quand ca fonctionnait pas, j'avais plein de bbbbbbbb qui s'affichait jusqu'à quand ca plante... ca doit tourner en rond ? Mais je comprends pas pourquoi 8O

je pense que tu dois exploser la pile de fonction.

je ne sais pas comment est declaré le type Population, mais essaye (si c'est pas un pointeur "masqué") de passer un pointeur sur Pop, plutot que Pop ...

si ça marche toujours pas ...
je pense que tu vas devoir re-ecrire ton algorithme en iteratif.

Bon beh je confirme le problème ne vient pas de la taille de la liste de départ que je passe mais le problème est au niveau de la fonction, dans la dernière boucle else, car parfois ca tourne en rond, ca ne s'arrete jamais, d'ou le plantage... :roll:

Quelqu'un pour m'aider ?

Merci Bonne fêtes de fin d'années...

Citation:

---

Envoyé par Dark_Ebola

(si c'est pas un pointeur "masqué")

---

Si :

Code:

---

1 2 3

Population p=Pop; [...] p->next = NULL;

---

Comment est généré ta liste à trier ? Il semblerai que tu tombe sur le pire des cas (liste totalement dans le désodre, par exemple) ce qui t'oblige à faire de nombreuses permutations et fait exploser la pile (ou dû moins ralenti ton programme).

sachant qu'il faut compter 3 variables de type Population par appel et que la taille de la pile s'exprime en kilo-octects (je viens de voir sur http://support.microsoft.com/ la valeur de 64 ko mais ce n'est qu'un exemple) tu peux vite savoir si tu explose la pile :P

Le mieux serait de revoir l'algo en commençant par le dé-récursifier

Euh déjà c'est quoi un pointeur masqué ?
Désolé mais je débute, c'est mon premier projet d'info :roll:

La liste est générée automatiquement, je ne sais pas comment expliquer, il faudrait que je mette toutes les fonctions avec mais cela revient presque à mettre tout le projet et je pense pas que quelqu'un ait vraiment le temps et l'envie de regarder mon projet entier, même s'il n'est pas très gros. :roll:

L'ennui c'est que l'énoncé est fait pour qu'on fasse cette fonction de façon récursive...

Mais le problème je pense, viens du fait que parfois ca appel continuellement la fonction sans s'arrêter,(ca reste dans le dernier else à l'infini) ca n'atteint pas la condition d'arrêt et d'ailleurs je ne comprends pas pourquoi. Peut etre que ma fonction pour séparer deux listes est mal faite ? :

Merci de votre aide...

Re Bonsoir,

Etant parti dans tous les sens au début, je vais essayer de redéfinir mon problème maintenant que je pense l'avoir localisé...

Donc pour commencer par le début : j’ai un projet d’info sur les algorithmes génétiques, dedans je dois faire un tri : le tri Quicksort de façon récursive…

Je travaille avec des listes chaînées.


Dans cette fonction Quicksort, j’utilise une autre fonction « separer » (qui permet de séparer une liste en 2 sous listes) et une fonction « fusion » (qui permet de coller 2 listes chaînées).

Alors mon problème c’est que des fois ma fonction Quicksort bug… en plaçant des printf dedans pour voir ou pouvez venir le problème, j’ai vu que parfois, la fonction s’appelait sans arrêt, les conditions d’arrêt ne sont jamais atteintes… mais ca je n’arrive pas à le comprendre, pour moi les conditions d'arrêt sont vraiments bien, peut-être incomplètes mais je ne sais pas…

A moins que le probleme vient d’une des 2 autres fonctions que j’utilise dedans mais j’ai fait pas mal d’essai avec et ca a toujours fonctionné donc je reste sur l’idée que le problème vient de la fonction Quicksort récursive qui, des fois, ne s’arrête pas et donc ca plante !!




Merci à vous

Bonnes fêtes

tu devrais essayer de suivre le deroulement de ton programme grace a un debugger en mode "pas a pas".

Je peux trouver ou un débugger ?

Code:

---

Pop = Pop->next;

---

ne modifie rien dans le contexte appelant. Il est vraissemblable que c'est lié à ton problème.

Si l'objectif n'est pas d'implémenter un quick sort mais de trier, il y a toujours qsort, qui évite d'avoir à réinventer la roue.

Faire un quick sort sur des listes chaînées est assez amusant; mais peu utile en pratique: sur des listes chaînées un merge sort est facile à implémenter et a des meilleures caractéristiques qu'un quick sort.

Citation:

---

Envoyé par gege2061

Le mieux serait de revoir l'algo en commençant par le dé-récursifier

---

Ca, c'est fonctionner à l'envers. Quick sort est un algorithme récursif et pas une itération cachée. Tant qu'il ne fonctionne pas, le dé-récursifier n'a aucun intérêt. On peut penser à le faire si effectivement on a vérifié que la pile explose.

ca y est j'ai trouvé le probleme :)

merci quand meme

++