Commentaires sur une source : QUICKSORT - NON RECURSIF

cs_Maroi Messages postés 10 Date d'inscription mercredi 30 décembre 2009 Statut Membre Dernière intervention 1 avril 2012
30 avril 2010 à 12:51

Merci bcp pour votre réponse, mais en fait je cherche un programme en C??

shenron666 Messages postés 229 Date d'inscription dimanche 14 septembre 2003 Statut Membre Dernière intervention 20 août 2014
29 avril 2010 à 20:53

je te conseille de passer par la stl en utilisant par exemple un std::vector<double> et la méthode de tri std::sort

cs_Maroi Messages postés 10 Date d'inscription mercredi 30 décembre 2009 Statut Membre Dernière intervention 1 avril 2012
29 avril 2010 à 20:41

Salut,
Est ce que vous pouvez donner un exemple de quicksort non récursif pr les réels?
Merci bcp

shenron666 Messages postés 229 Date d'inscription dimanche 14 septembre 2003 Statut Membre Dernière intervention 20 août 2014
14 mars 2006 à 12:01

Salut les gens, bon j'ai pris le temps ce matin de venir aux nouvelles et j'ai vu le post de Noxk
J'avais un big problème avec mon algo lorsqu'on triait 2 fois de suite un tableau : dépassement de pile
du coup je n'avais pas fait attention qu'en plus je n'avais pas mis la bonne version en ligne qui, en effet ne trait pas
j'ai pas l'air con -__-

bref, j'ai corrigé à partir d'un algo repris sur un site très bien fait :
http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

le tri de 10 millions de valeurs me donne les temps suivants (en ms) :
nickydaquick (RHASH = 10000) : 797
Brunews : 2360
qsort CRT : 2906
mon tri récursif : 4750
avec la std : 1187 (std::sort d'un vector)
avec la std : 2671 (std::sort_heap d'un vector)

j'ai aussi essayé de trier plusieurs fois de suite un tableau, vu que je rencontrais des problèmes avec mon algo
bizarrement le tri de nickydaquick prend de plus en plus de temps, je n'ai pas regardé pourquoi
Le tri de Brunews s'en sort très bien

au final je trouve l'algo de brunews plutot performant, dommage que je sois si buté sur les goto ^_^
je me répète en disant que je trouve la méthode de nickydaquick intéressante
dès que j'aurai plus de temps je regarderai si je peux faire la même chose pour un CArray

Noxk Messages postés 10 Date d'inscription dimanche 26 février 2006 Statut Membre Dernière intervention 27 mars 2007
14 mars 2006 à 09:28

Salut Nicky,

J'ai effectué les test comme tu l'indiquais et les temps donnés pour le tri sont reellement meilleur mais y a un bogue, le tri est partiellement effectué. Ceci provient du fait que tu as oublié de remettre cursor a sa position final quand tu realloues la memoire.

Ca se corrige en remplacant les "*(cursor++)" par des "*(cursor + i++)" et ensuite dans la condition "if" mettre "*(cursor + i);"

Mais meme avec ca on remarque un probleme, tu rentres trop souvent dans la condition "if" de realloc et ca bouffe un temps enorme.Ce que je te propose, vu que tu utilise dans ton algo une pile, que tu ne depiles jamais, c'est justement s'en servir comme d'une pile qu'on depile et plus besoin de realloué la memoire, le seul probleme reside dans le fait de definir une taille de la pile suffisante.

Je me permets de mettre le code corrigé a ma manière et qui ressemble un peu a celui que j'ai écrit sur l'aspect pile/depile.

#define RHASH 100000

void quicksort(int* const tablo, const int first , const int last)
{
//first = premier index du tableau
//last = dernier index du tableau
int debut;
int fin;
int begin;
int end;
int pivot;
int temp;
int i=0;

int index=0;
int size=0;
int capacite = RHASH+2;

//allocation de la file
int* queue = NULL;
int* cursor;
int* indexc;

queue = (int*)malloc(capacite*sizeof(int));

if(queue == NULL)
return;

cursor = queue;
indexc = queue;

*(cursor + i++) = first; //sauvegarde du debut du tablo a trier
*(cursor + i++) = last; //sauvegarde de la fin du tablo a trier
index = 0;
size = 2;

do
{
//debut = *(indexc++); //recuperation de l'indice de debut
//fin = *(indexc++); //recuperation de l'indice de fin
fin = *(cursor + --i); //recuperation de l'indice de fin
debut = *(cursor + --i); //recuperation de l'indice de debut

index+=2;

if(debut < fin)
{
begin = debut;
end = fin;
pivot = tablo[fin];//on prend le dernier element comme valeur pivot

do
{
//progresser jusqu'a un element superieur ou egal au pivot
while ( (begin < fin) && (tablo[begin]<=pivot) )
begin++;
//progresser jusqu'a un element inferieur ou egal au pivot
while ( (end > begin) && (tablo[end]>=pivot) )
end--;

//echanger les 2 elements qui sont dans le mauvais ordre
//comparativement au pivot
if (begin < end)
{
temp = tablo[end];
tablo[end] = tablo[begin];
tablo[begin] = temp;
}

}while(begin < end);//continuer a parcourir le tablo

//mettre le pivot a sa place dans le tableau trie
temp = tablo[fin];
tablo[fin] = tablo[begin];
tablo[begin] = temp;

//sauvegarder les indexes des prochains tris a faire
// dans les sous-tableaux prochains
// a savoir : a gauche du pivot , puis a droite du pivot

//sauvegarde du debut du sous-tableau a trier => a gauche du pivot
*(cursor + i++) = debut;
//sauvegarde de la fin du sous-tableau a trier => a gauche du pivot
*(cursor + i++) = begin-1;

//sauvegarde du debut du sous-tableau a trier => a droite du pivot
*(cursor + i++) = begin+1;
//sauvegarde de la fin du sous-tableau a trier => a droite du pivot
*(cursor + i++) = fin;
size+=4;

// if(size==capacite)
// {
// capacite += RHASH;
// cout << "rehash" << endl;
// queue = (int*)realloc(queue,capacite*sizeof(int));
// cursor = queue;
// indexc = &cursor[index];
//*(cursor + i);
// if(queue == NULL)
// return;
// }
}
}
while(index<size);
cursor = NULL;
indexc = NULL;
free(queue);
}

Reste plus qu'a trouver un matheux pour trouver la formule de la taille de la pile en rapport avec celle du tableau :)

Sinon au niveau des score maintenant tu es meilleur que le mien mais reste tres legerement en dessous de ceux de BruNew.

cs_fuliculi Messages postés 43 Date d'inscription lundi 19 avril 2004 Statut Membre Dernière intervention 3 mai 2010 6
14 mars 2006 à 08:47

De quel algo parle tu? je pense que le mieux est de donner les temps de chaque algo (qui fonctionne) sur le même ordi (et même conditions) pour pouvoir comparer, et éventuellement la config de m'ordi (genre si t'as 16Mo de RAM, faut pas s'étonner que ce soit plus lent ;)
L'idéal est de faire quelques tests à blanc (histoire de récupérer de la mémoire inutilisée) et de donner la moyenne, le min et le max des temps suivants, et ce, pour chaque algo.
Si quelqu'un trouve l'envie et le temps, ça m'intéresserait :)

nickydaquick Messages postés 416 Date d'inscription vendredi 31 janvier 2003 Statut Membre Dernière intervention 19 décembre 2013 3
14 mars 2006 à 01:52

Je suis desole mais tes temps ne sont pas exacts sur le mien ( mon ordi ) je suis en dessous des 1.6 sur un random de 10 millions de int , si tu utilises une tranche de reallocation moindre ( de l'ordre de la centaine de milliers )

Noxk Messages postés 10 Date d'inscription dimanche 26 février 2006 Statut Membre Dernière intervention 27 mars 2007
13 mars 2006 à 13:35

Je viens de tester les algo de quicksort sur 10 000 000 d'int dans l'ordre d'arrivé, c'est :

BruNews : 1.485 seconde
le mien : 1.578
nickydaquick : 1.687
qsort : 2.859

J'ai pas testé celui de Fuliculi vu que ce n'est pas un quicksort bien que pour les int il soit plus interressant que le notre.

Noxk Messages postés 10 Date d'inscription dimanche 26 février 2006 Statut Membre Dernière intervention 27 mars 2007
11 mars 2006 à 16:56

shenron666, ton algo de tri je viens de le tester il ne marche pas, certe il est rapide mais en sorti c'est pas trié, il y a certainement quelque chose a revoir.

cs_fuliculi Messages postés 43 Date d'inscription lundi 19 avril 2004 Statut Membre Dernière intervention 3 mai 2010 6
10 mars 2006 à 09:31

En effet, il a ses limites. J'ai un manque de mémoire virtuelle si je teste avec 100 millions de valeurs.

Pour la partie photonmapping de mon raytracer, je devais trier les photons dans l'ordre de proximité d'un point. Le problème est que les distances sont en float (besoin de précision) et l'algo ne gère que les entiers. J'ai donc combiné deux algo de tri pour pouvoir profiter des performances du tri à panier. Pour trier des float, donc, je place les float dans des paniers qui ne correspondent pas à une valeur entière mais à une plage de valeurs réelles (bornées) et je remplis. Ensuite, je tri le contenu de chaque panier (tri à bulle) et je n'ai plus qu'à les vider comme dans l'algo que j'ai codé. Selon les cas, si vous n'avez pas besoin d'un tri parfait, on peut se limiter au tri à panier sans second tri.

Une autre solution à laquelle j'ai pensée consiste à convertir les float en entier avec un facteur (int = float *1000 par exemple). La encore, le tri n'est pas parfait (manque de précision) mais ça dépend encore de l'usage que l'on souhaite en faire. Je n'ai pas pris le temps de tester cette solution.

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
9 mars 2006 à 23:00

Je viens de tester, nickel pour la vitesse (presque 12 fois plus vite que celui que j'ai mis en lien).
Dommage qu'il y ait cette alloc mémoire qui peut rater (par exemple sur une plage full 32 bits on ne passe pas) mais enfin devrait aller dans beaucoup de cas, vraiment très bien.

cs_fuliculi Messages postés 43 Date d'inscription lundi 19 avril 2004 Statut Membre Dernière intervention 3 mai 2010 6
9 mars 2006 à 16:29

Pardon (je ne spam pas) j'ai oublié l'option d'optimisation (/O2), j'ai donc 140ms contre 3500ms avec 10 millions de valeurs.

cs_fuliculi Messages postés 43 Date d'inscription lundi 19 avril 2004 Statut Membre Dernière intervention 3 mai 2010 6
9 mars 2006 à 16:27

J'ai ces temps là avec l'algo de nickydaquick

400 ms pour 1 millions de valeurs (26x plus de temps)
5200 ms pour 10 millions de valeurs (24x plus de temps)

Et vous?

cs_fuliculi Messages postés 43 Date d'inscription lundi 19 avril 2004 Statut Membre Dernière intervention 3 mai 2010 6
9 mars 2006 à 16:18

Pour info, j'ai ces temps là avec mon code en release :
15 ms pour 1 millions de valeurs
219 ms pour 10 millions de valeurs

(Pentium 4 2.6GHz)

Y'a moyen d'optimiser en remplaçant certains long en int, char, short (selon vos valeur) mais attention, la plupart doivent être conservés pour accepter les long tableaux (int=65536 valeurs max)

cs_fuliculi Messages postés 43 Date d'inscription lundi 19 avril 2004 Statut Membre Dernière intervention 3 mai 2010 6
9 mars 2006 à 16:04

Allez hop, c'est codé à l'arrache mais j'ai pris le temps de tester un peu quand même...

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <time.h>

void tri(long *tab, long size)
{
if (size<=0 || tab==NULL)
return;

long min = tab[0];
long max = tab[0];
long i, j;

// Recherche les bornes de la liste
for (i=0; i<size; i++)
{
if (tab[i]<min) min=tab[i];
if (tab[i]>max) max=tab[i];
}

if (min==max)
return;

// Un panier par valeur possible entre le min et le max
long *paniers = new long[max-min+1];
memset(paniers, 0, (max-min+1)*sizeof(long));

// Ajouter un jeton dans le panier de la valeur (min premier panier, max dernier panier)
for (i=0; i<size; i++)
paniers[tab[i]-min]++;

long numVal = 0;

// Remplir le tableau d'entrée avec les paniers en partant du premier (ou du dernier pour un tri décroissant)
for (i=0; i<max-min+1; i++)
// Copier autant de fois la valeur du panier qu'il contient de jetons
for (j=0; j<paniers[i]; j++)
tab[numVal++] = min+i;

delete [] paniers;
}

//#define PRINT

void main (void)
{
long max = 1000000;
long *values = new long[max];
long i;

srand((unsigned)time(NULL));

for (i=0; i<max; i++)
values[i] = (long)rand();

#ifdef PRINT
for (i=0; i<max; i++)
printf("in : %d ", values[i]);
#endif

long startTime = clock();
tri(values, max);
long stopTime = clock();

#ifdef PRINT
for (i=0; i<max; i++)
printf("out : %d\n", values[i]);
#endif

printf("Temps ecoule : %d ms", stopTime - startTime);

delete [] values;
}

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
9 mars 2006 à 15:48

Un exemple serait le bienvenu stp.

cs_fuliculi Messages postés 43 Date d'inscription lundi 19 avril 2004 Statut Membre Dernière intervention 3 mai 2010 6
9 mars 2006 à 15:30

L'algo le plus efficace à ce jour (il me semble) est le tri à panier. Ca ne s'applique qu'au tri de nombres entiers (pas de réel) et c'est terriblement simple et rapide.

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
9 mars 2006 à 15:17

http://bnmvp.free.fr/SortInt.zip

Pourriez vous comparer avec vos procédures ? merci d'avance.
Je n'affiche que les millisecondes du tri pour 100 000 ou 1 000 000, pour le résutat trié dans listbox suffit de remettre les lignes du code en service mais pas utile ici.

svp ne ralez pour l'asm, il n'entre pour rien dans le tri, juste pour fournir zip minuscule.

nickydaquick Messages postés 416 Date d'inscription vendredi 31 janvier 2003 Statut Membre Dernière intervention 19 décembre 2013 3
7 mars 2006 à 16:07

Ok Shenron , tu gagnes , je vais te mettre un version rapide du Tri rapide , sans bug ... tu pourras faire les tests. Toutes mes excuses si je t'ai mal compris mais mon but etait initialement de montrer un algorithme , donc une logique revue du quicksort. Je recorrigerait donc ma source , pour que tu puisses faire des test sur autant de nombres que tu veux. Je mettrai aussi des resultats en comparatif avec la fonction qsort() de vc++6.0. Donne moi juste 5 minutes.

shenron666 Messages postés 229 Date d'inscription dimanche 14 septembre 2003 Statut Membre Dernière intervention 20 août 2014
7 mars 2006 à 15:16

attends, si t'es pas prêt à accepter les critiques "non positives" concernant ton programme arrêtes de programmer
là je t'ai prévenu qu'il y avait un bug, tu le prend mal, et c'est moi qui ait un problème ?
si les tests temporels te posent problème tu n'as qu'a faire un tri bulle, le qsort est intéressant pour sa rapidité (quand il fonctionne) et comme l'a dit BruNews, pourquoi l'avoir recodé si le qsort des CRT existe ?
ah mais oui ok j'ai compris, en fait c'est pas un code source c'est un algo que tu as déposé
mea culpa, je préfère m'arrêter là
bonne continuation

nickydaquick Messages postés 416 Date d'inscription vendredi 31 janvier 2003 Statut Membre Dernière intervention 19 décembre 2013 3
7 mars 2006 à 14:57

En fait je viens de comprendre ton pb, tu voudrais un code que tu puisse carrement coller sans avoir a comprendre quoi que ce soit , faire un test si ca marche Bingo. Dans ce cas demande le moi je te le donne , optimisé et avec les comparaisons temporels en ms.
J'attends de tes news

PS: De nos jour les gens ne savent plus la signification du mot algorithme ...

shenron666 Messages postés 229 Date d'inscription dimanche 14 septembre 2003 Statut Membre Dernière intervention 20 août 2014
7 mars 2006 à 13:16

"et donne nous des resultats temporels"
euh, tu as lu mon post ? c'est fait, à titre "illustratif et comprehensif" si tu veux

si ton code n'est pas exempt de bug il va causer des problèmes dans le heap, et si tu déposes un code sans zip, comment je le récupère sans faire un copier coller ?
ton code fait une allocation :
const int taille = 3*(last-first+1);
int* queue = NULL;

queue = new int [taille];

et lorsque tu écris dans queue, tu dépasses la "taille" que tu as allouée, là il y a un gros problème puisque tu vas aller écraser d'autres données
tu me dis que c'est à moi de débugguer ton code ? :-/

quand à déterminer la taille du heap à réserver... ????
tu peux m'expliquer ?
non mais je demande parceque qsort fonctionne, lui, :

#define TAILLE_TABLEAU 100000L
DWORD test_tri()
{
int* arTest = new int[TAILLE_TABLEAU];

srand(GetTickCount());
for(int i=0; i < TAILLE_TABLEAU; i++)
arTest[ i ] = rand();

DWORD tStart = GetTickCount();
qsort(arTest, TAILLE_TABLEAU, sizeof(int), qsort_compare);
return (GetTickCount() - tStart);
}

nickydaquick Messages postés 416 Date d'inscription vendredi 31 janvier 2003 Statut Membre Dernière intervention 19 décembre 2013 3
7 mars 2006 à 12:37

MErci pour tous vos commentaires... Je tenais a te dire shenron666, que ce code a ete depose ici a titre illustratif et comprehensif. La taille du tableau est uniquement suggestif alors arrete de faire des copier - coller et inspire toi de ce code pour ameliorer le tien. Toi ki fait par exemple des tests de rapidite , arrete de nous dire si le test plante ( parce que tu n'as certainement pas determine la taille du heap a reserver au depart du prog ) , et donne nous des resultats temporels
Merci

shenron666 Messages postés 229 Date d'inscription dimanche 14 septembre 2003 Statut Membre Dernière intervention 20 août 2014
7 mars 2006 à 12:16

goto est à éviter, oui le cpu fait des sauts qu'on ne voit pas, il n'empêche qu'un code orienté objet propre et maintenable ne contient pas de goto
c'est une règle fondamentale du C++ en tout cas
le fait est que le C++ n'a pas récupéré du C que des bonnes choses

ton programme est en C ou ne contient rien de particulier en C++
tu utilises une structure pour stocker tes données
si tu utilisais une classe, pourrais-tu encore utiliser qsort pour trier tes données ?
pire encore si tu stockes des pointeurs vers des objets

pour en revenir au prog de nickydaquick, je trouve que c'est son approche qui est intéressante
il n'y a pas qu'une seule et unique manière de programmer donc moi ça me plait de voir des sources comme la sienne
reste à débugguer le code ^^

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
7 mars 2006 à 11:53

qsort est un algo générique, on en a le code donc on le dévie pour le spécialiser:
http://www.cppfrance.com/code.aspx?id=11151

'goto' indique que c'est de la daube ? alors change de taf, un cpu ne comprend que cela les sauts de code, pas parce qu'on ne les voit pas que le compilo écrira autre chose.

shenron666 Messages postés 229 Date d'inscription dimanche 14 septembre 2003 Statut Membre Dernière intervention 20 août 2014
7 mars 2006 à 11:30

Oui bah l'implémentation qsort de la CRT je veux pas dire mais c'est un peu de la merde
enfin juste un peu ^^
tu veux un exemple ? ligne 249 : "goto recurse;" arghhhh
euh, c'est du basic ?

non sans dec' même la source que j'ai déposé est plus rapide sur un tableau de 1 millions d'int :
- qsort : 297 ms
- CSortedArray : 172 ms
un bon 70% de différences

enfin bon, je sais qu'il y en a à qui ça suffira mais à mon taf je traite des centaines de Mo de données et on en arrive à plusieurs Go, avec des progs en C++, MFC, POO le qsort est comment dire ? trop léger
bah c'est du C quoi (qui a dit basic ? ^^)

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
7 mars 2006 à 10:28

Vraiment je ne copprends pas votre problème.
Le tableau à trier existe déjà puisqu'on le reçoit en param donc aucun prob mémoire vu q'il n'y a aucune alloc à faire pour un quicksort, suffit de regarder l'implem de qsort() de la CRT.

shenron666 Messages postés 229 Date d'inscription dimanche 14 septembre 2003 Statut Membre Dernière intervention 20 août 2014
7 mars 2006 à 10:12

J'ai copié collé ton tri dans un programme pour le tester et voir s'il était plus rapide qu'un tri que j'avais fait : http://www.cppfrance.com/code.aspx?ID=33969

ton tri plante avec plus de 100000 éléments
en debug, ton size++ dépasse taille

j'ai également noté que ton allocation est énorme par rapport à la taille du tableau initial

mon code de test est le suivant :
#define TAILLE_TABLEAU 100000L
DWORD test_tri()
{
int* arTest = new int[TAILLE_TABLEAU];

srand(GetTickCount());
for(int i=0; i < TAILLE_TABLEAU; i++)
arTest[ i ] = rand();

DWORD tStart = GetTickCount();
TriSortNonRecursif(arTest, 0, TAILLE_TABLEAU - 1);
return (GetTickCount() - tStart);
}

vecchio56 Messages postés 6535 Date d'inscription lundi 16 décembre 2002 Statut Membre Dernière intervention 22 août 2010 14
4 mars 2006 à 16:54

Les allocations dans la pile sont bien moins couteux que dans le tas. Mais ici il n'y a c'est vrai qu'une allocation dans le tas, ce qui doit sans doute compenser en général

nickydaquick Messages postés 416 Date d'inscription vendredi 31 janvier 2003 Statut Membre Dernière intervention 19 décembre 2013 3
4 mars 2006 à 16:23

Merci pour ton commentaire Shenron666. En effet il faudrait faire dess tests de rapidite , mais je suis pas mal sur que cette implementation serait plus rapide. En ce qui concerne
mon allocation memoire avec "queue" c'est vrai c'en est une , mais elle n'a lieu qu'une seule fois, contrairement a des appels recursifs.
En ce qui concerne la STL , j'aurais pu utilise la conteneur deque , mais la encore j'aurais fait appel a des fonction push_back, front , et pop_front ce qui n'est pas tres interessant. En gros je voulais limiter le plus possible les appels de fonction . Nous appelons ca chez nous : La programmation en DUR :D ... mdr
Salut

shenron666 Messages postés 229 Date d'inscription dimanche 14 septembre 2003 Statut Membre Dernière intervention 20 août 2014
4 mars 2006 à 10:09

Source intéressante de par ton approche ;-)

Il faudrait faire des tests de rapidité entre ta fonction et la même en mode récursif pour voir s'il y a réellement une différence de vitesse à ton avantage.
Surtout que tu parles de réallocation mais tu en fais toi aussi avec "queue"

Dommage que tu n'utilises pas la stl mais ce n'est qu'un détail

nickydaquick Messages postés 416 Date d'inscription vendredi 31 janvier 2003 Statut Membre Dernière intervention 19 décembre 2013 3
3 mars 2006 à 18:40

Excuse - moi si je n'ai pas ete tres clair dans mes propos... Je suis heureux que nous nous comprenions :D .
Merci encore pour ta critique

vecchio56 Messages postés 6535 Date d'inscription lundi 16 décembre 2002 Statut Membre Dernière intervention 22 août 2010 14
3 mars 2006 à 18:37

Tu dis "à cause des sauvegardes sur la pile (...) et des réallocations mémoires" donc je me disais que tu parlais d'allocations ailleurs que dans la pile

nickydaquick Messages postés 416 Date d'inscription vendredi 31 janvier 2003 Statut Membre Dernière intervention 19 décembre 2013 3
3 mars 2006 à 18:16

une allocation memoire peut se faire soi dans la pile soi dans le tas, l'un dans l'autre une demande est toujours faite... tu ne crois pas ?
Merci

vecchio56 Messages postés 6535 Date d'inscription lundi 16 décembre 2002 Statut Membre Dernière intervention 22 août 2010 14
3 mars 2006 à 17:51

Je sais ce qu'est une réallocation, mais dans le cas de la récursivité, tout se passe dans la pile, donc ya jamais d'allocation de mémoire ailleurs

nickydaquick Messages postés 416 Date d'inscription vendredi 31 janvier 2003 Statut Membre Dernière intervention 19 décembre 2013 3
3 mars 2006 à 17:47

reallocations => allocations + desallocations
lorsque tu fais un appel de fonctions, a moins que je ne me trompe , l'adresse de retour de la fonction appelante , les arguments de la fonction appelee sont mis en memoire ainsi que les variables. Ce qui veut dire qu'a chaque appel ton programme fait une demande de memoire. Puis tu desalloues cette memoire au retour de la fonction. Un probleme que tu pourrais rencontrer c'est une limitation de ta recursivite dans l'echec d'une allocation pour un appel recursif. Dans mon programme tu te limiterais a moins d'appels d'allocations memoire.
En fait les appels recursifs du quicksort sont remplaces ici par des acces memoires ( notre espace est deja alloue d'un bloc dans le tas) et des test plutot qu'a des allocations-desallocations memoires repetitives
J'espere avoir repondu a ta question. Merci et aurevoir

vecchio56 Messages postés 6535 Date d'inscription lundi 16 décembre 2002 Statut Membre Dernière intervention 22 août 2010 14
3 mars 2006 à 10:40

Tu dis que les appels de fonctions sont pénalisants à cause des sauvegardes sur la pile et des réallocations mémoire. Qu'est ce que tu entends par réallocations mémoire?

QUICKSORT - NON RECURSIF

Votre réponse

Discussions similaires