Help :: Tri-Fusion itératif !!

Signaler
Messages postés
6
Date d'inscription
jeudi 3 avril 2003
Statut
Membre
Dernière intervention
5 avril 2003
-
Messages postés
6
Date d'inscription
jeudi 3 avril 2003
Statut
Membre
Dernière intervention
5 avril 2003
-
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 ^¤^
A voir également:

7 réponses

Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
20
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...
Messages postés
6
Date d'inscription
jeudi 3 avril 2003
Statut
Membre
Dernière intervention
5 avril 2003

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 ^¤^
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
20
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...
Messages postés
6
Date d'inscription
jeudi 3 avril 2003
Statut
Membre
Dernière intervention
5 avril 2003

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 ^¤^
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
20
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...
Messages postés
3
Date d'inscription
jeudi 1 mai 2003
Statut
Membre
Dernière intervention
10 mars 2008

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
Messages postés
6
Date d'inscription
jeudi 3 avril 2003
Statut
Membre
Dernière intervention
5 avril 2003

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 ^¤^