Pourquoi ça sature la pile? [C++] - C++ - Programmation
Marsh Posté le 27-03-2003 à 22:52:06
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.
Marsh Posté le 27-03-2003 à 22:54:58
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
Marsh Posté le 27-03-2003 à 23:04:27
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
Marsh Posté le 28-03-2003 à 16:35:25
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:
Code :
|
Marsh Posté le 28-03-2003 à 17:41:47
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)
Marsh Posté le 28-03-2003 à 18:23:13
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 !
Marsh Posté le 28-03-2003 à 18:42:05
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
Marsh Posté le 28-03-2003 à 18:42:18
pColumns[i].fHeight sont des floats.
pColumnsOrder[i] sont des unsigned int.
Marsh Posté le 29-03-2003 à 10:34:01
Alload a écrit : (enfin un QuickSOrt quoi ) |
Moi je parie que tu es étudiant, car sinon tu utiliserais "std::sort" :-)
Marsh Posté le 29-03-2003 à 10:42:18
kenshiro182 a écrit : |
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.
Marsh Posté le 29-03-2003 à 10:51:25
c'est bien ce qu'on pensait. utilise le std::sort, il est plus rapide, fonctionnel et adaptable
Marsh Posté le 29-03-2003 à 12:15:58
Alload a écrit : 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. |
"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".
Marsh Posté le 29-03-2003 à 13:13:28
Alload a écrit : c'est pas moi qui l'ai écris |
si ce n'est pas pour un tp, utilise qsort. http://msdn.microsoft.com/library/ [...] _qsort.asp
Marsh Posté le 29-03-2003 à 13:14:50
Alload a écrit : j'avais besoin d'un tri très rapide. |
le plus rapide (en n) est le bytesort, aussi appellé radix. fais une recherche, ça a déjà été abordé plusieurs fois ici.
Marsh Posté le 29-03-2003 à 13:45:04
youdontcare a écrit : 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
Marsh Posté le 30-03-2003 à 00:23:07
++Taz a écrit : 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
Marsh Posté le 30-03-2003 à 01:50:46
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 ...
Marsh Posté le 30-03-2003 à 01:57:04
theShOcKwAvE a écrit : 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) |
http://www.stereopsis.com/radix.html
LeGreg
Marsh Posté le 30-03-2003 à 03:17:50
Reply
Marsh Posté le 27-03-2003 à 22:47:30
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.