Help :: Tri-Fusion itératif !!

Salut !!
Je planche actuellement sur une version itérative du Tri-Fusion, et y a un pb : je ne vois pas comment écrire la fonction fusion qui se charge de trier/fusionner deux listes d'éléments non-triés !!
Qqn aurait un algo (en C) ou une piste à me lancer svp ?? Merci d'avance !!

^?^ Daarkon ^?^

Voila le quicksort issu de la CRT, aucune recursion.

void SmallSort(int *lo, int *hi)
{
int *p, *max;
int tmp;
while(hi > lo) {
max = lo;
for(p = lo + 1; p <= hi; p++) {
if(*p > *max) max = p;
}
tmp = *max; *max = *hi; *hi = tmp;
hi--;
}
}

void QuickSort(int *base, unsigned num)
{
int *lo, *hi; /* ends of sub-array currently sorting */
int *mid; /* points to middle of subarray */
int *loguy, *higuy; /* traveling pointers for partition step */
unsigned size; /* size of the sub-array */
int *lostk[30], *histk[30];
int stkptr; /* stack for saving sub-array to be processed */
int tmp;
/* Note: the number of stack entries required is no more than
1 + log2(size), so 30 is sufficient for any array */
if(num < 2) return; /* nothing to do */
stkptr = 0; /* initialize stack */
lo = base; hi = base + num - 1;
recurse:
size = (hi - lo) / sizeof(int) + 1; /* number of el's to sort */
/* below a certain size, it is faster to use a O(n^2) sorting method */
if(size <= 8) SmallSort(lo, hi);
else {
mid = lo + (size / 2); /* find middle element */
tmp = *mid; *mid = *lo; *lo = tmp;
loguy = lo; higuy = hi + 1;
/* higuy decreases and loguy increases on every iteration,
so loop must terminate. */
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; /* save big recursion for later */
}
if(loguy < hi) {lo = loguy; goto recurse;} /* do small recursion */
}
else {
if(loguy < hi) {
lostk[stkptr] = loguy; histk[stkptr] = hi;
++stkptr; /* save big recursion for later */
}
if(lo + 1 < higuy) {hi = higuy - 1; goto recurse;} /* do small recursion */
}
}
--stkptr;
if(stkptr >= 0) {
lo = lostk[stkptr];
hi = histk[stkptr];
goto recurse; /* pop subarray from stack */
}
}

BruNews, ciao...


-------------------------------
Réponse au message :
-------------------------------

> Salut !!
> Je planche actuellement sur une version itérative du Tri-Fusion, et y a un pb : je ne vois pas comment écrire la fonction fusion qui se charge de trier/fusionner deux listes d'éléments non-triés !!
> Qqn aurait un algo (en C) ou une piste à me lancer svp ?? Merci d'avance !!
>
> ^?^ Daarkon ^?^

hmmm oui ... why not, mais il faut une fonction qui soit linéaire (impératif, pour conserver la complexité Nlog(N) du tri-fusion) et qui ne ne teste qu'une fois chaque valeur !! et ce, sans aucune récursivité ni aucun "goto" ... lol

^?^ Daarkon ^?^


-------------------------------
Réponse au message :
-------------------------------

> Voila le quicksort issu de la CRT, aucune recursion.
>
> void SmallSort(int *lo, int *hi)
> {
> int *p, *max;
> int tmp;
> while(hi > lo) {
> max = lo;
> for(p = lo + 1; p <= hi; p++) {
> if(*p > *max) max = p;
> }
> tmp = *max; *max = *hi; *hi = tmp;
> hi--;
> }
> }
>
> void QuickSort(int *base, unsigned num)
> {
> int *lo, *hi; /* ends of sub-array currently sorting */
> int *mid; /* points to middle of subarray */
> int *loguy, *higuy; /* traveling pointers for partition step */
> unsigned size; /* size of the sub-array */
> int *lostk[30], *histk[30];
> int stkptr; /* stack for saving sub-array to be processed */
> int tmp;
> /* Note: the number of stack entries required is no more than
> 1 + log2(size), so 30 is sufficient for any array */
> if(num < 2) return; /* nothing to do */
> stkptr = 0; /* initialize stack */
> lo = base; hi = base + num - 1;
> recurse:
> size = (hi - lo) / sizeof(int) + 1; /* number of el's to sort */
> /* below a certain size, it is faster to use a O(n^2) sorting method */
> if(size <= 8) SmallSort(lo, hi);
> else {
> mid = lo + (size / 2); /* find middle element */
> tmp = *mid; *mid = *lo; *lo = tmp;
> loguy = lo; higuy = hi + 1;
> /* higuy decreases and loguy increases on every iteration,
> so loop must terminate. */
> 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; /* save big recursion for later */
> }
> if(loguy < hi) {lo = loguy; goto recurse;} /* do small recursion */
> }
> else {
> if(loguy < hi) {
> lostk[stkptr] = loguy; histk[stkptr] = hi;
> ++stkptr; /* save big recursion for later */
> }
> if(lo + 1 < higuy) {hi = higuy - 1; goto recurse;} /* do small recursion */
> }
> }
> --stkptr;
> if(stkptr >= 0) {
> lo = lostk[stkptr];
> hi = histk[stkptr];
> goto recurse; /* pop subarray from stack */
> }
> }
>
> BruNews, ciao...
>
>
> -------------------------------
> Réponse au message :
> -------------------------------
>
> > Salut !!
> > Je planche actuellement sur une version itérative du Tri-Fusion, et y a un pb : je ne vois pas comment écrire la fonction fusion qui se charge de trier/fusionner deux listes d'éléments non-triés !!
> > Qqn aurait un algo (en C) ou une piste à me lancer svp ?? Merci d'avance !!
> >
> > ^?^ Daarkon ^?^
>

Tu as vu une recursivite dans ce code ?
Pour goto suffit de pas le regarder, ton compilo en mettra en place des if case etc...
Tu dvrais faire tests avec et comparer les temps.
La meme traitee toute en interne.
void QuickSort(int *base, unsigned num)
{
int *lo, *hi; /* ends of sub-array currently sorting */
int *mid; /* points to middle of subarray */
int *loguy, *higuy; /* traveling pointers for partition step */
unsigned size; /* size of the sub-array */
int *lostk[30], *histk[30];
int stkptr; /* stack for saving sub-array to be processed */
int tmp;
/* Note: the number of stack entries required is no more than
1 + log2(size), so 30 is sufficient for any array */
if(num < 2) return; /* nothing to do */
stkptr = 0; /* initialize stack */
lo = base; hi = base + num - 1;
recurse:
size = (hi - lo) / sizeof(int) + 1; /* number of el's to sort */
/* below a certain size, it is faster to use a O(n^2) sorting method */
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); /* find middle element */
tmp = *mid; *mid = *lo; *lo = tmp;
loguy = lo; higuy = hi + 1;
/* higuy decreases and loguy increases on every iteration,
so loop must terminate. */
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; /* save big recursion for later */
}
if(loguy < hi) {lo = loguy; goto recurse;} /* do small recursion */
}
else {
if(loguy < hi) {
lostk[stkptr] = loguy; histk[stkptr] = hi;
++stkptr; /* save big recursion for later */
}
if(lo + 1 < higuy) {hi = higuy - 1; goto recurse;} /* do small recursion */
}
fromSmall:
--stkptr;
if(stkptr >= 0) {
lo = lostk[stkptr];
hi = histk[stkptr];
goto recurse; /* pop subarray from stack */
}
}

BruNews, ciao...


-------------------------------
Réponse au message :
-------------------------------

> hmmm oui ... why not, mais il faut une fonction qui soit linéaire (impératif, pour conserver la complexité Nlog(N) du tri-fusion) et qui ne ne teste qu'une fois chaque valeur !! et ce, sans aucune récursivité ni aucun "goto" ... lol
>
> ^?^ Daarkon ^?^
>
>
> -------------------------------
> Réponse au message :
> -------------------------------
>
> > Voila le quicksort issu de la CRT, aucune recursion.
> >
> > void SmallSort(int *lo, int *hi)
> > {
> > int *p, *max;
> > int tmp;
> > while(hi > lo) {
> > max = lo;
> > for(p = lo + 1; p <= hi; p++) {
> > if(*p > *max) max = p;
> > }
> > tmp = *max; *max = *hi; *hi = tmp;
> > hi--;
> > }
> > }
> >
> > void QuickSort(int *base, unsigned num)
> > {
> > int *lo, *hi; /* ends of sub-array currently sorting */
> > int *mid; /* points to middle of subarray */
> > int *loguy, *higuy; /* traveling pointers for partition step */
> > unsigned size; /* size of the sub-array */
> > int *lostk[30], *histk[30];
> > int stkptr; /* stack for saving sub-array to be processed */
> > int tmp;
> > /* Note: the number of stack entries required is no more than
> > 1 + log2(size), so 30 is sufficient for any array */
> > if(num < 2) return; /* nothing to do */
> > stkptr = 0; /* initialize stack */
> > lo = base; hi = base + num - 1;
> > recurse:
> > size = (hi - lo) / sizeof(int) + 1; /* number of el's to sort */
> > /* below a certain size, it is faster to use a O(n^2) sorting method */
> > if(size <= 8) SmallSort(lo, hi);
> > else {
> > mid = lo + (size / 2); /* find middle element */
> > tmp = *mid; *mid = *lo; *lo = tmp;
> > loguy = lo; higuy = hi + 1;
> > /* higuy decreases and loguy increases on every iteration,
> > so loop must terminate. */
> > 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; /* save big recursion for later */
> > }
> > if(loguy < hi) {lo = loguy; goto recurse;} /* do small recursion */
> > }
> > else {
> > if(loguy < hi) {
> > lostk[stkptr] = loguy; histk[stkptr] = hi;
> > ++stkptr; /* save big recursion for later */
> > }
> > if(lo + 1 < higuy) {hi = higuy - 1; goto recurse;} /* do small recursion */
> > }
> > }
> > --stkptr;
> > if(stkptr >= 0) {
> > lo = lostk[stkptr];
> > hi = histk[stkptr];
> > goto recurse; /* pop subarray from stack */
> > }
> > }
> >
> > BruNews, ciao...
> >
> >
> > -------------------------------
> > Réponse au message :
> > -------------------------------
> >
> > > Salut !!
> > > Je planche actuellement sur une version itérative du Tri-Fusion, et y a un pb : je ne vois pas comment écrire la fonction fusion qui se charge de trier/fusionner deux listes d'éléments non-triés !!
> > > Qqn aurait un algo (en C) ou une piste à me lancer svp ?? Merci d'avance !!
> > >
> > > ^?^ Daarkon ^?^
> >
>

y a pas de récursivité c'est vrai ... mais meme si le compilateur remplacera les goto par autre chose, qd mon prof verra le source il gueulera pcq on n'a jamais utilisé aucun goto ;-)
en fait ... voilà comment je pars pr le tri/fusion itératif :
je considère mon tableau comme une suite de "boites" de 1 élément, donc ces boites contiennent bien des éléments triés (un élément seul est toujours trié !!) ... suite à quoi j'augmente par 2 la taille des listes, pour trier/fusionner des listes de 2 éléments et ainsi de suite, en prenant en compte la possibilité que la taille des listes soit > taille du tableau, auquel cas je rectifie dans ma fonction "fusion" ... mais le pb est que soit cette fonction ne s'arrete pas (alors qu'il y a bien un critère d'arret), soit elle me remplace des éléments du tableau de base par des 0 !!!
voici la version actuelle de Fusionner (note : t2 est un tableau créé dans la fonction tri/fusion en temporaire, et t est le tableau initial a trier) :

// trie et fusionne en une passe les éléments de 2 sous-tableaux

void fusionner(int *t, int *t2 , int deb, int longueur, const long int tailleTab)
{
// [deb ; deb+longueur] = [i ; iMax] U [j ; jMax]
int i ;
int iMax = deb + longueur/2 - 1 ;
int j = deb + longueur/2 ; // ou j = iMax+1
int jMax = deb + longueur ;
int fait = 0 ;

// cas extremes si on dépasse la taille du tableau
if ( iMax >= tailleTab )
iMax = tailleTab-1 ;

if ( jMax >= tailleTab )
jMax = tailleTab-1 ;

// recopie du tableau initial ds le tableau temporaire
for(i=0 ; i<longueur ; i++)
{
t2 = t[i] ;
}

i = deb ;

while( fait == 0 )
{
if(i<=iMax && j<=jMax)
{
if( t2[i]<t2[j] ) // t2[i] < t2[j] ? si oui t2[i] -> t[i]
{
t[i] = t2[i] ;
i=i++ ;
}
else // sinon t2[j] -> t[i] ;
{
t[i] = t2[j] ;
i=i++ ;
j=j++ ;
}
}
else
{
if(i<=iMax)
{
t[i] = t2[i] ;
i++ ;
}
else if (j<=jMax)
{
t[i] = t2[j] ;
i++ ;
j++ ;
}
else
fait == 1 ;
}
}
}

where is the bug ??

^?^ Daarkon ^?^


-------------------------------
Réponse au message :
-------------------------------

> Tu as vu une recursivite dans ce code ?
> Pour goto suffit de pas le regarder, ton compilo en mettra en place des if case etc...
> Tu dvrais faire tests avec et comparer les temps.
> La meme traitee toute en interne.
> void QuickSort(int *base, unsigned num)
> {
> int *lo, *hi; /* ends of sub-array currently sorting */
> int *mid; /* points to middle of subarray */
> int *loguy, *higuy; /* traveling pointers for partition step */
> unsigned size; /* size of the sub-array */
> int *lostk[30], *histk[30];
> int stkptr; /* stack for saving sub-array to be processed */
> int tmp;
> /* Note: the number of stack entries required is no more than
> 1 + log2(size), so 30 is sufficient for any array */
> if(num < 2) return; /* nothing to do */
> stkptr = 0; /* initialize stack */
> lo = base; hi = base + num - 1;
> recurse:
> size = (hi - lo) / sizeof(int) + 1; /* number of el's to sort */
> /* below a certain size, it is faster to use a O(n^2) sorting method */
> 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); /* find middle element */
> tmp = *mid; *mid = *lo; *lo = tmp;
> loguy = lo; higuy = hi + 1;
> /* higuy decreases and loguy increases on every iteration,
> so loop must terminate. */
> 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; /* save big recursion for later */
> }
> if(loguy < hi) {lo = loguy; goto recurse;} /* do small recursion */
> }
> else {
> if(loguy < hi) {
> lostk[stkptr] = loguy; histk[stkptr] = hi;
> ++stkptr; /* save big recursion for later */
> }
> if(lo + 1 < higuy) {hi = higuy - 1; goto recurse;} /* do small recursion */
> }
> fromSmall:
> --stkptr;
> if(stkptr >= 0) {
> lo = lostk[stkptr];
> hi = histk[stkptr];
> goto recurse; /* pop subarray from stack */
> }
> }
>
> BruNews, ciao...
>
>
> -------------------------------
> Réponse au message :
> -------------------------------
>
> > hmmm oui ... why not, mais il faut une fonction qui soit linéaire (impératif, pour conserver la complexité Nlog(N) du tri-fusion) et qui ne ne teste qu'une fois chaque valeur !! et ce, sans aucune récursivité ni aucun "goto" ... lol
> >
> > ^?^ Daarkon ^?^
> >
> >
> > -------------------------------
> > Réponse au message :
> > -------------------------------
> >
> > > Voila le quicksort issu de la CRT, aucune recursion.
> > >
> > > void SmallSort(int *lo, int *hi)
> > > {
> > > int *p, *max;
> > > int tmp;
> > > while(hi > lo) {
> > > max = lo;
> > > for(p = lo + 1; p <= hi; p++) {
> > > if(*p > *max) max = p;
> > > }
> > > tmp = *max; *max = *hi; *hi = tmp;
> > > hi--;
> > > }
> > > }
> > >
> > > void QuickSort(int *base, unsigned num)
> > > {
> > > int *lo, *hi; /* ends of sub-array currently sorting */
> > > int *mid; /* points to middle of subarray */
> > > int *loguy, *higuy; /* traveling pointers for partition step */
> > > unsigned size; /* size of the sub-array */
> > > int *lostk[30], *histk[30];
> > > int stkptr; /* stack for saving sub-array to be processed */
> > > int tmp;
> > > /* Note: the number of stack entries required is no more than
> > > 1 + log2(size), so 30 is sufficient for any array */
> > > if(num < 2) return; /* nothing to do */
> > > stkptr = 0; /* initialize stack */
> > > lo = base; hi = base + num - 1;
> > > recurse:
> > > size = (hi - lo) / sizeof(int) + 1; /* number of el's to sort */
> > > /* below a certain size, it is faster to use a O(n^2) sorting method */
> > > if(size <= 8) SmallSort(lo, hi);
> > > else {
> > > mid = lo + (size / 2); /* find middle element */
> > > tmp = *mid; *mid = *lo; *lo = tmp;
> > > loguy = lo; higuy = hi + 1;
> > > /* higuy decreases and loguy increases on every iteration,
> > > so loop must terminate. */
> > > 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; /* save big recursion for later */
> > > }
> > > if(loguy < hi) {lo = loguy; goto recurse;} /* do small recursion */
> > > }
> > > else {
> > > if(loguy < hi) {
> > > lostk[stkptr] = loguy; histk[stkptr] = hi;
> > > ++stkptr; /* save big recursion for later */
> > > }
> > > if(lo + 1 < higuy) {hi = higuy - 1; goto recurse;} /* do small recursion */
> > > }
> > > }
> > > --stkptr;
> > > if(stkptr >= 0) {
> > > lo = lostk[stkptr];
> > > hi = histk[stkptr];
> > > goto recurse; /* pop subarray from stack */
> > > }
> > > }
> > >
> > > BruNews, ciao...
> > >
> > >
> > > -------------------------------
> > > Réponse au message :
> > > -------------------------------
> > >
> > > > Salut !!
> > > > Je planche actuellement sur une version itérative du Tri-Fusion, et y a un pb : je ne vois pas comment écrire la fonction fusion qui se charge de trier/fusionner deux listes d'éléments non-triés !!
> > > > Qqn aurait un algo (en C) ou une piste à me lancer svp ?? Merci d'avance !!
> > > >
> > > > [i]^?^ Daarkon ^?^
> > >
> >
>

Tu m'aurais dit de suite que c'est pour l'ecole qui ne veut pas de goto, je n'insistais pas.
Pas le temps d'aller + loin pour l'instant.
BruNews, ciao...


-------------------------------
Réponse au message :
-------------------------------

> y a pas de récursivité c'est vrai ... mais meme si le compilateur remplacera les goto par autre chose, qd mon prof verra le source il gueulera pcq on n'a jamais utilisé aucun goto ;-)
> en fait ... voilà comment je pars pr le tri/fusion itératif :
> je considère mon tableau comme une suite de "boites" de 1 élément, donc ces boites contiennent bien des éléments triés (un élément seul est toujours trié !!) ... suite à quoi j'augmente par 2 la taille des listes, pour trier/fusionner des listes de 2 éléments et ainsi de suite, en prenant en compte la possibilité que la taille des listes soit > taille du tableau, auquel cas je rectifie dans ma fonction "fusion" ... mais le pb est que soit cette fonction ne s'arrete pas (alors qu'il y a bien un critère d'arret), soit elle me remplace des éléments du tableau de base par des 0 !!!
> voici la version actuelle de Fusionner (note : t2 est un tableau créé dans la fonction tri/fusion en temporaire, et t est le tableau initial a trier) :
>
> // trie et fusionne en une passe les éléments de 2 sous-tableaux
>
> void fusionner(int *t, int *t2 , int deb, int longueur, const long int tailleTab)
> {
> // [deb ; deb+longueur] = [i ; iMax] U [j ; jMax]
> int i ;
> int iMax = deb + longueur/2 - 1 ;
> int j = deb + longueur/2 ; // ou j = iMax+1
> int jMax = deb + longueur ;
> int fait = 0 ;
>
> // cas extremes si on dépasse la taille du tableau
> if ( iMax >= tailleTab )
> iMax = tailleTab-1 ;
>
> if ( jMax >= tailleTab )
> jMax = tailleTab-1 ;
>
> // recopie du tableau initial ds le tableau temporaire
> for(i=0 ; i<longueur ; i++)
> {
> t2 = t[i] ;
> }
>
> i = deb ;
>
> while( fait == 0 )
> {
> if(i<=iMax && j<=jMax)
> {
> if( t2[i]<t2[j] ) // t2[i] < t2[j] ? si oui t2[i] -> t[i]
> {
> t[i] = t2[i] ;
> i=i++ ;
> }
> else // sinon t2[j] -> t[i] ;
> {
> t[i] = t2[j] ;
> i=i++ ;
> j=j++ ;
> }
> }
> else
> {
> if(i<=iMax)
> {
> t[i] = t2[i] ;
> i++ ;
> }
> else if (j<=jMax)
> {
> t[i] = t2[j] ;
> i++ ;
> j++ ;
> }
> else
> fait == 1 ;
> }
> }
> }
>
> where is the bug ??
>
> ^?^ Daarkon ^?^
>
>
> -------------------------------
> Réponse au message :
> -------------------------------
>
> > Tu as vu une recursivite dans ce code ?
> > Pour goto suffit de pas le regarder, ton compilo en mettra en place des if case etc...
> > Tu dvrais faire tests avec et comparer les temps.
> > La meme traitee toute en interne.
> > void QuickSort(int *base, unsigned num)
> > {
> > int *lo, *hi; /* ends of sub-array currently sorting */
> > int *mid; /* points to middle of subarray */
> > int *loguy, *higuy; /* traveling pointers for partition step */
> > unsigned size; /* size of the sub-array */
> > int *lostk[30], *histk[30];
> > int stkptr; /* stack for saving sub-array to be processed */
> > int tmp;
> > /* Note: the number of stack entries required is no more than
> > 1 + log2(size), so 30 is sufficient for any array */
> > if(num < 2) return; /* nothing to do */
> > stkptr = 0; /* initialize stack */
> > lo = base; hi = base + num - 1;
> > recurse:
> > size = (hi - lo) / sizeof(int) + 1; /* number of el's to sort */
> > /* below a certain size, it is faster to use a O(n^2) sorting method */
> > 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); /* find middle element */
> > tmp = *mid; *mid = *lo; *lo = tmp;
> > loguy = lo; higuy = hi + 1;
> > /* higuy decreases and loguy increases on every iteration,
> > so loop must terminate. */
> > 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; /* save big recursion for later */
> > }
> > if(loguy < hi) {lo = loguy; goto recurse;} /* do small recursion */
> > }
> > else {
> > if(loguy < hi) {
> > lostk[stkptr] = loguy; histk[stkptr] = hi;
> > ++stkptr; /* save big recursion for later */
> > }
> > if(lo + 1 < higuy) {hi = higuy - 1; goto recurse;} /* do small recursion */
> > }
> > fromSmall:
> > --stkptr;
> > if(stkptr >= 0) {
> > lo = lostk[stkptr];
> > hi = histk[stkptr];
> > goto recurse; /* pop subarray from stack */
> > }
> > }
> >
> > BruNews, ciao...
> >
> >
> > -------------------------------
> > Réponse au message :
> > -------------------------------
> >
> > > hmmm oui ... why not, mais il faut une fonction qui soit linéaire (impératif, pour conserver la complexité Nlog(N) du tri-fusion) et qui ne ne teste qu'une fois chaque valeur !! et ce, sans aucune récursivité ni aucun "goto" ... lol
> > >
> > > ^?^ Daarkon ^?^
> > >
> > >
> > > -------------------------------
> > > Réponse au message :
> > > -------------------------------
> > >
> > > > Voila le quicksort issu de la CRT, aucune recursion.
> > > >
> > > > void SmallSort(int *lo, int *hi)
> > > > {
> > > > int *p, *max;
> > > > int tmp;
> > > > while(hi > lo) {
> > > > max = lo;
> > > > for(p = lo + 1; p <= hi; p++) {
> > > > if(*p > *max) max = p;
> > > > }
> > > > tmp = *max; *max = *hi; *hi = tmp;
> > > > hi--;
> > > > }
> > > > }
> > > >
> > > > void QuickSort(int *base, unsigned num)
> > > > {
> > > > int *lo, *hi; /* ends of sub-array currently sorting */
> > > > int *mid; /* points to middle of subarray */
> > > > int *loguy, *higuy; /* traveling pointers for partition step */
> > > > unsigned size; /* size of the sub-array */
> > > > int *lostk[30], *histk[30];
> > > > int stkptr; /* stack for saving sub-array to be processed */
> > > > int tmp;
> > > > /* Note: the number of stack entries required is no more than
> > > > 1 + log2(size), so 30 is sufficient for any array */
> > > > if(num < 2) return; /* nothing to do */
> > > > stkptr = 0; /* initialize stack */
> > > > lo = base; hi = base + num - 1;
> > > > recurse:
> > > > size = (hi - lo) / sizeof(int) + 1; /* number of el's to sort */
> > > > /* below a certain size, it is faster to use a O(n^2) sorting method */
> > > > if(size <= 8) SmallSort(lo, hi);
> > > > else {
> > > > mid = lo + (size / 2); /* find middle element */
> > > > tmp = *mid; *mid = *lo; *lo = tmp;
> > > > loguy = lo; higuy = hi + 1;
> > > > /* higuy decreases and loguy increases on every iteration,
> > > > so loop must terminate. */
> > > > 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; /* save big recursion for later */
> > > > }
> > > > if(loguy < hi) {lo = loguy; goto recurse;} /* do small recursion */
> > > > }
> > > > else {
> > > > if(loguy < hi) {
> > > > lostk[stkptr] = loguy; histk[stkptr] = hi;
> > > > ++stkptr; /* save big recursion for later */
> > > > }
> > > > if(lo + 1 < higuy) {hi = higuy - 1; goto recurse;} /* do small recursion */
> > > > }
> > > > }
> > > > --stkptr;
> > > > if(stkptr >= 0) {
> > > > lo = lostk[stkptr];
> > > > hi = histk[stkptr];
> > > > goto recurse; /* pop subarray from stack */
> > > > }
> > > > }
> > > >
> > > > BruNews, ciao...
> > > >
> > > >
> > > > -------------------------------
> > > > Réponse au message :
> > > > -------------------------------
> > > >
> > > > > Salut !!
> > > > > Je planche actuellement sur une version itérative du Tri-Fusion, et y a un pb : je ne vois pas comment écrire la fonction fusion qui se charge de trier/fusionner deux listes d'éléments non-triés !!
> > > > > Qqn aurait un algo (en C) ou une piste à me lancer svp ?? Merci d'avance !!
> > > > >
> > > > > [i]^?^ Daarkon ^?^
> > > >
> > >
> >
>

T'as que regarder sur celui de Smimit ;)
J'éspére que t'as réussi sinon, m'sieur négre y vas pô aimer ;)

A+ Damz



-------------------------------
Réponse au message :
-------------------------------

> Salut !!
> Je planche actuellement sur une version itérative du Tri-Fusion, et y a un pb : je ne vois pas comment écrire la fonction fusion qui se charge de trier/fusionner deux listes d'éléments non-triés !!
> Qqn aurait un algo (en C) ou une piste à me lancer svp ?? Merci d'avance !!
>
> ^?^ Daarkon ^?^

Hoohooooo Damieeen !!
T'es dingue, je vais pas prendre un algo de qqn d'autre, et encore moins celui d'un nul comme Smimite !! mdrr
Nan mais c'est bon, g trouvé depuis pas mal de temps déjà (un dessin sur papier a suffi !!) ;-) Meme le rapport est prêt ... hihi

^¤^ Daarkon ^¤^


-------------------------------
Réponse au message :
-------------------------------

> T'as que regarder sur celui de Smimit ;)
> J'éspére que t'as réussi sinon, m'sieur négre y vas pô aimer ;)
>
> A+ Damz
>
>
>
> -------------------------------
> Réponse au message :
> -------------------------------
>
> > Salut !!
> > Je planche actuellement sur une version itérative du Tri-Fusion, et y a un pb : je ne vois pas comment écrire la fonction fusion qui se charge de trier/fusionner deux listes d'éléments non-triés !!
> > Qqn aurait un algo (en C) ou une piste à me lancer svp ?? Merci d'avance !!
> >
> > ^?^ Daarkon ^?^