Quicksort sans récurisivité ( appel a sa propre fonction) en pur C

Question

Voila le topo , sachant que la récursivité est un  gouffre de mémoire sinon une m**** ,je cherche une fonction de tri rapide(QSort) en pur C sans avoir recours a cette cette m**** de récursivité , j'ai bout regarde plusieurs implémentation elles sont toutes récursif.
Les seules codes que j'ai trouve sont celles de la libc de FreeBSD et celle de Zend(moteur php) qui ne sont pas recursif , mais alors la vaut meme pas regarder , le code est trufé de goto et utilise un zillion de varaiable tmp . alors si quelqu'un a une simple idée d'un quicksort non recrusif ca serait géniale.

A Vos LEs StuDioS

coucou747 · Answer

salut

pour commencer, la recursivite n'est pas si lente que ca, et dans le cas d'un qsort, ca va te bouffer un truc genre une cinquantaine d'octets * log(n) en stack... c'est pas enorme hein...

ensuite, beaucoup de fonctions sont tail-recursives, et sont donc compilees comme si elles n'etaient pas recursives (mais c'est pas le cas du Qsort)

pour le Qsort, si tu veux faire ca, alors tu dois avoir un tableau d'indexes ou tu stoques tes "bouts de tableaux pas encore tries" et c'est pas forcement mieux.

BruNews · Answer

Tu trouveras un Qsort sans récurrence ici: VILLES ET CODES POSTAUX (WIN32) http://www.cppfrance.com/code.aspx?id=11151 Exemple sur un simple tableau de INT32: void __stdcall QuickSort(int *base, unsigned int num) { int *lo, *hi; int *mid; int *loguy, *higuy; unsigned int size; int *lostk[30], *histk[30]; int stkptr; int tmp; if(num < 2) return; stkptr = 0; lo base; hi base + num - 1; recurse: size = (hi - lo) / sizeof(int) + 1; if(size <= 8) { while(hi > lo) { mid = lo; for(loguy = lo + 1; loguy <= hi; loguy++) if(*loguy > *mid) mid = loguy; tmp *mid; *mid *hi; *hi = tmp; hi--; } goto fromSmall; } mid = lo + (size / 2); tmp *mid; *mid *lo; *lo = tmp; loguy lo; higuy hi + 1; for(;;) { do { loguy++; } while(loguy <= hi && (*loguy <= *lo)); do { higuy--; } while(higuy > lo && (*(int*)higuy >= *(int*)lo)); if(higuy < loguy) break; tmp *loguy; *loguy *higuy; *higuy = tmp; } tmp *lo; *lo *higuy; *higuy = tmp; if(higuy - 1 - lo >= hi - loguy) { if(lo + 1 < higuy) { lostk[stkptr] = lo; histk[stkptr] = higuy - 1; ++stkptr; } if(loguy < hi) {lo = loguy; goto recurse;} } else { if(loguy < hi) { lostk[stkptr] = loguy; histk[stkptr] = hi; ++stkptr; } if(lo + 1 < higuy) {hi = higuy - 1; goto recurse;} } fromSmall: --stkptr; if(stkptr >= 0) { lo = lostk[stkptr]; hi = histk[stkptr]; goto recurse; } } ciao... BruNews, MVP VC++

xtremejames183 · Answer

Interessant je vais voir ca .merci

Quicksort sans récurisivité ( appel a sa propre fonction) en pur C

3 réponses

Votre réponse

Discussions similaires