Help :: Tri-Fusion itératif !!
daarkon666
Messages postés
6
Date d'inscription
jeudi 3 avril 2003
Statut
Membre
Dernière intervention
5 avril 2003
-
3 avril 2003 à 14:15
daarkon666 Messages postés 6 Date d'inscription jeudi 3 avril 2003 Statut Membre Dernière intervention 5 avril 2003 - 1 mai 2003 à 18:13
daarkon666 Messages postés 6 Date d'inscription jeudi 3 avril 2003 Statut Membre Dernière intervention 5 avril 2003 - 1 mai 2003 à 18:13
7 réponses
BruNews
Messages postés
21040
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
3 avril 2003 à 14:26
3 avril 2003 à 14:26
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...
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...
daarkon666
Messages postés
6
Date d'inscription
jeudi 3 avril 2003
Statut
Membre
Dernière intervention
5 avril 2003
3 avril 2003 à 16:02
3 avril 2003 à 16:02
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 ^¤^
^¤^ Daarkon ^¤^
BruNews
Messages postés
21040
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
3 avril 2003 à 16:14
3 avril 2003 à 16:14
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...
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...
daarkon666
Messages postés
6
Date d'inscription
jeudi 3 avril 2003
Statut
Membre
Dernière intervention
5 avril 2003
3 avril 2003 à 16:37
3 avril 2003 à 16:37
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 ^¤^
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 ^¤^
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
BruNews
Messages postés
21040
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
3 avril 2003 à 17:26
3 avril 2003 à 17:26
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...
Pas le temps d'aller + loin pour l'instant.
BruNews, ciao...
SuperMonkey
Messages postés
3
Date d'inscription
jeudi 1 mai 2003
Statut
Membre
Dernière intervention
10 mars 2008
1 mai 2003 à 13:50
1 mai 2003 à 13:50
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
J'éspére que t'as réussi sinon, m'sieur négre y vas pô aimer ;)
A+ Damz
daarkon666
Messages postés
6
Date d'inscription
jeudi 3 avril 2003
Statut
Membre
Dernière intervention
5 avril 2003
1 mai 2003 à 18:13
1 mai 2003 à 18:13
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 ^¤^
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 ^¤^