Alors voilà, j'ai une pointeur pointant sur une liste de unsigned int, j'utilise ce pointeur dans une fonction qui fait un QuickSort sur la liste asignée au pointeur.
 
Bon, je lance la fonction tout ce passe bien, tout est trié. Je relance la fonction et là il y a une surchage de la pile!
 
Pourtant, si avant de lancer la fonction de trie je détruis la liste associée au pointeur et en réassigne une nouvelle je peux lancer la fonction un nombre de fois illimité. Bien sûr ça marche mais je ne trouve pas ça élégant...
 
Je ne comprend pas pourquoi il y a une saturation si je ne détruis pas à chaque fois ma liste sachant que je fais seulement quelques swaps (enfin un QuickSOrt quoi ) qui ne surchage pas la pile lors d'une première itération, alors pourquoi lors d'un second passage il y a une surchage?
 
Pouvez-vous m'aider à comprendre? Merci.

Ca depend de comment tu as codé ton QuickSort. Il est très facile de tomber sur la version dans lequel le pire des cas correspond à une liste déjà triée. Autrement dis, quand tu tries 2 fois d'affilé, la deuxième fois ton QuickSort se tape une complexité de O(n²) avec plus d'it"ration et donc plus d'appel récursifs successifs.

Ah ça doit être ça sachant que quand je détruis pas ma liste, je ne la modifie pas donc elle est déjà triée.
 
PS: je me dite pas que c'est con de trier une liste qu'on sait triée, c'est seulement des tests pour le moment

la question c'est pourquoi TON implementation de quicksort
sature la pile sur une liste deja triee..
 
Et franchement on ne peut pas vraiment repondre sans voir ton implementation..
 
LeGreg

Alors voilà ma fonction qui fait le QuickSort, c'est pas moi qui l'ai écris, je l'ai pompé sur le net et je l'ai modifié pour qu'elle puisse trier la hauteur de plusieurs colonnes que j'utilise dans mon programme. Le but est de mettre dans la liste pColumnsOrder l'ordre des colonnes de la plus petite à la plus grande:
 

tu pourrais preciser tes types de données, on sait jamais, juste comme ça
 
le mieux: tu mais des cout partout ou tu prends ton debuggeur et tu vas voire que ta recursion est infinie ou alors trop grande pour ton systeme (limitation de la  taille de la pile)

Taz> Remplace "mais" par "mets", parce que là, le plafond a failli être repeint de mon sang tellement j'ai bondi...
 
edit> Et vire ce 'e' à 'voire' que je ne saurais voir !

Comme tu choisis pour pivot le premier element de la liste, c'est justement que le pire des cas pour le QuickSort avec une liste triee.
 
Pour information, dans cette situation tu vas probablement faire dans les n(n-1)/2 appels recursifs. Pas ettonant que ca finisse par peter

pColumns[i].fHeight sont des floats.
pColumnsOrder[i] sont des unsigned int.

Moi je parie que tu es étudiant, car sinon tu utiliserais "std::sort" :-)

Oui et non Suis pas en filière info, en fait j'utilise ce tri dans un programme fait pour un TIPE (exposé) et j'avais besoin d'un tri très rapide. J'ai pensé au std::sort, mais première je ne sais pas si il est plus rapide que QuickSort et deuxièmement il faut que tri des structures alors je ne savais pas comment utiliser la fonction.

c'est bien ce qu'on pensait. utilise le std::sort, il est plus rapide, fonctionnel et adaptable

"std::sort" a une complexité en n*log(n) (c'est à dire que le nombre d'opérations nécessaires pour n élément est de l'ordre de n*log(n), sauf cas rares). std::sort peut être implémenté par un algo "quick sort".
"std::sort" est plus rapide car contrairement à "quicksort", la fonction de comparaison peut etre "inlinée".

si ce n'est pas pour un tp, utilise qsort. http://msdn.microsoft.com/library/ [...] _qsort.asp

le plus rapide (en n) est le bytesort, aussi appellé radix. fais une recherche, ça a déjà été abordé plusieurs fois ici.

hey, on parle de tri généralisé ici, obéissant à un critère de haut niveau tel que less, tu peux essayer ton bytesort autant de fois que tu veux, tu n'arriveras jamais à rien. => std::sort

 
je ne vois pas en quoi il est de plus haut niveau
ce n'est jamais qu'une comparaison de flottants..
 
Certes en utilisant, le std::sort tu as un algo générique
que tu peux réutiliser librement.. C'est d'ailleurs l'objectif de la STL, pas forcément compatible avec la meilleure performance dans le cas général.
 
LeGreg

fo pas pousser non plus

std::sort std::sort  ...
 
ok std::jsuisdehors
 
 
 
 
 
 
 
 
...  

Au fait ... J'vois pas vraiment comment on peut faire un byte sort sur des flottants ... (si je ne me trompe pas, même en les comparant méchamment bit à bit, ca colle pas car l'exposant dans les nombres floattants est sur les bits de poids le plus faible)
 
Edit : une faute d'orthographe ...

 
http://www.stereopsis.com/radix.html
 
LeGreg

 
 
merci !