Discussion :

[bj303931]

Bonjour, j'essaie de faire le tri par fusion mais ça ne marche pas.

Explication du tri par fusion.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdio.h>
#include <stdlib.h>
 
void fusion (int * tab, int n){
 
	int i;
	int memoire=0;
 
for(i=0; i<n/5; i++){ 
// Je compare le 1 et 2.
	if(*tab>*tab++){ 
		*tab=memoire;
		*tab=*tab++;
		*tab++;
//position:2
		*tab=memoire;
			}
	*tab++;
//position:3
	*tab++;
//position:4
//Je compare le 4 et le 5
 
	if(*tab>*tab++){ 
		*tab=memoire;
		*tab=*tab++;
		*tab++;
		*tab=memoire;
			}
 
//Je reviens à la position initiale	
	for(i=0; i<5; i++){*tab--;}
 
//Je compare les 3 premiers
	if(*tab>*tab++){ 
		*tab=memoire;
		*tab=*tab++;
		*tab++;
		*tab=memoire;
			}
 
	if(*tab>*tab++){ 
		*tab=memoire;
		*tab=*tab++;
		*tab++;
		*tab=memoire;
			}
 
//Je reviens à la position initiale	
	for(i=0; i<5; i++){*tab--;}
 
//Je compare les 5 premiers.
	for(i=0; i<5; i++){
 
	if(*tab>*tab++){ 
		*tab=memoire;
		*tab=*tab++;
		*tab++;
		*tab=memoire;
			}
			   }
 
				}
for (i=0; i<n; i++){
 
	printf("%d", *tab);
	*tab--;
}
}
 
int main(){
 
	int i;
	int *tab=NULL;
	tab=malloc(1000*sizeof(int));
 
	for(i=0; i<10; i++){*tab++=rand()%5+1;}
 
	for(i=0; i<10; i++){*tab--;}	
 
	for(i=0; i<10; i++){
		printf("%d ", *tab);
		*tab++;
			   }
 
	fusion(tab, 10);
 
return 0;}

Avec 4 2 3 1 4 1 2 3 5 2
Ca renvoie: 0025321413

[Médinoc]

Il est bizarre, ton tri fusion. Normalement, il est fait récursivement...
De plus, pour le faire à vitesse optimale, il me semble qu'il faut éviter de le faire in-place (personnellement je le fais sur deux buffers).

[bj303931]

Il y ce code.

Mais je ne comprend pas la fonction fusion.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
    #include <stdlib.h>
 
    void fusion (int *a, int n, int m) {
        int i, j, k;
        int *x = malloc(n * sizeof (int)); //Il sort d'où le x?
        for (i = 0, j = m, k = 0; k < n; k++) { //Pas compris: trop d'inconnues
            x[k] = j == n      ? a[i++]  // Pourquoi, il y a des points d'interrogation? 
                 : i == m      ? a[j++]
                 : a[j] < a[i] ? a[j++]
                 :               a[i++]; //Pourquoi, il y a : ?
        }
        for (i = 0; i < n; i++) {
            a[i] = x[i]; // Le truc vraiment incompréhensible! :mrgreen:
        }
        free(x);
    }
 
 
 
    void tri_fusion (int *liste, int taille) {
        if (taille < 2) return;
        int milieu = taille / 2;
        tri_fusion(liste, milieu);
        tri_fusion(liste milieu, taille - milieu);
        fusion(liste, taille, milieu);
    }

[Médinoc]

Ça, ça ressemble plus à un vrai tri-fusion (mais sous-optimisé parce qu'il alloue son second buffer à chaque fois).

Par contre, je suis 100% d'accord avec toi, ce code est imbitable! Variables d'une seule lettre, abus de l'opérateur conditionnel ternaire...

Je vais voir si je peux faire un truc plus clair.

[Médinoc]

Ceci devrait être plus facile à comprendre

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//Techniquement, on pourrait se passer de offsetDest, puisqu'il devrait toujours être égal à ixDebut
void fusion(int const* pcSource, size_t ixDebut, size_t ixMilieu, size_t ixFin, int *pDest, size_t offsetDest)
{
	size_t ixGauche = ixDebut, ixDroite = ixMilieu;
	size_t ixDest = 0;
	while(ixGauche < ixMilieu && ixDroite < ixFin) //Tant qu'on n'a pas lu complètement les deux plages du tableau
	{
		if(ixGauche >= ixMilieu)
		{
			//On a lu toute la partie gauche, il faut donc ajouter la partie droite au tableau destination
			int valeurRestante = pcSource[ixDroite++];
			pDest[offsetDest + ixDest++] = valeurRestante;
		}
		else if(ixDroite >= ixFin)
		{
			//On a lu toute la partie droite, il faut donc ajouter la partie gauche au tableau destination
			int valeurRestante = pcSource[ixGauche++];
			pDest[offsetDest + ixDest++] = valeurRestante;
		}
		else
		{
			//Il en reste des deux côtés: Il faut comparer les valeurs (sans les consommer)
			//et ajouter la plus petite à la destination (en la consommant)
			int valeurGauche = pcSource[ixGauche];
			int valeurDroite = pcSource[ixDroite];
			int valeurMin;
			//Je pourrais utiliser l'opérateur conditionel ternaire ici,
			//mais c'est déjà assez compliqué avec les post-incrémentations
			if(valeurGauche <= valeurDroite)
				valeurMin = pcSource[ixGauche++];
			else
				valeurMin = pcSource[ixDroite++];
			pDest[offsetDest + ixDest++] = valeurMin;
		}
	}//while
}
 
 
void triFusionRec(int *pTableau, size_t ixDebut, size_t ixFin, int *pAutreTableau)
{
	if(ixFin - ixDebut <= 1)
	{
		if(ixFin - ixDebut > 0)
			pTableau[ixDebut] = pAutreTableau[ixDebut];
		return;
	}
 
	{
		size_t ixMilieu = ixDebut + (ixFin - ixDebut)/2;
		//On trie les sous-tableaux en inversant l'ordre, les résultats triés seront donc dans pAutreTableau
		triFusionRec(pAutreTableau, ixDebut, ixMilieu, pTableau);
		triFusionRec(pAutreTableau, ixMilieu, ixFin, pTableau);
		//Fusionne les sous-tableaux triés (dans pAutreTableau) vers pTableau
		fusion(pAutreTableau, ixDebut, ixMilieu, ixFin, pTableau, ixDebut);
	}
}
 
int triFusion(int *pTableau, size_t taille)
{
	int* pAutreTableau = malloc(taille * sizeof(int))
	if(pAutreTableau==NULL)
		return -1;
 
 
	memcpy(pAutreTableau, pTableau, taille * sizeof(int));
 
	triFusionRec(pTableau, 0, taille, pAutreTableau);
 
	free(pAutreTableau);
	return 0;
}

[Pyramidev]

Bonjour.

Il y ce code.

Mais je ne comprend pas la fonction fusion.

Explication préliminaire sur l'opérateur ternaire :
L'expression "Condition ? A : B" équivaut à "A" si Condition est vraie, "B" si Condition est fausse.

Exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
int max(int x, int y) {
    return x > y ? x : y;
}

Code équivalent :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
int max(int x, int y) {
    if(x > y)
        return x;
    else
        return y;
}

L'expression "Condition1 ? A : Condition2 ? B : C" est évaluée comme "Condition1 ? A : (Condition2 ? B : C)".
Elle équivaut à "A" si Condition1 est vraie, "(Condition2 ? B : C)" si Condition1 est fausse.
Du coup, elle équivaut à :
-"A" si Condition1 est vraie,
-"B" si Condition1 est fausse et si Condition2 est vraie,
-"C" si Condition1 est fausse et si Condition2 est fausse.

Exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
int max(int x, int y, int z) {
    return
        x > y && x > z ? x :
        y > z          ? y :
                         z;
}

Code équivalent :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
int max(int x, int y) {
    if(x > y && x > z)
        return x;
    else if(y > z)
        return y;
    else
        return z;
}

A présent, voici le code de la fonction fusion qui t'embête, avec des commentaires ajoutés.
(J'ai juste changé l'ordre de quelques initialisations au début pour commenter plus facilement.)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*!
 * \brief Trier un tableau qui est la concaténation de deux sous-tableaux déjà triés.
 * \param a pointeur vers le 1er élément du tableau
 * \param n taille du tableau
 * \param m indice du premier élément du sous-tableau de droite
 */
void fusion(int *a, int n, int m)
{
    // D'abord, on met le résultat du tri dans un tableau intermédiaire x.
    int *x = malloc(n * sizeof (int));
    int i = 0; // indice du plus petit élément du sous-tableau de gauche pas encore dans x
    int j = m; // indice du plus petit élément du sous-tableau de droite pas encore dans x
    for(int k = 0; k < n; k++) { // Pour chaque indice du tableau x...
        x[k] =
            // Prenons le plus petit élément des deux sous-tableaux pas encore dans x.
            j == n ?        // Si tous les éléments du sous-tableau de droite sont déjà dans x,
                a[i++]      // on prend le plus petit élément du sous-tableau de gauche pas encore dans x.
            : i == m ?      // Sinon, si tous les éléments du sous-tableau de gauche sont déjà dans x,
                a[j++]      // on prend le plus petit élément du sous-tableau de droite pas encore dans x.
            : a[j] < a[i] ? // Sinon, on compare le plus petit élément pas encore dans x de chacun
                            // des deux sous-tableaux et on prend le plus petit des deux.
                a[j++]
            :
                a[i++];
    }
 
    // Maintenant que le tableau x contient le résultat du tri, on copie le tableau x dans le tableau a puis on détruit x.
    for (i = 0; i < n; i++) {
        a[i] = x[i];
    }
    free(x);
}

[Mckinl3y]

Bonjour,

voici un autre code de fusion, je ne comprends pas comment il fonctionne, même en essayant de compiler sur papier.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
static void fusion(int t[], int t1[], int t2[])
	{
		int i = 0, i1 = 0, i2 = 0;
		while( i1 < t1.length && i2 < t2.length )
		{
			if( t1[i1] < t2[i2] )
	  			t[i++] = t1[i1++]; // que va t il se passer à la compilation de cette partie ? t[i]= t1[i1] puis i++ et i1++ ?
 
			else
				t[i++] = t2[i2++];
 
		}	
 
 
 
	  	while( i1 < t1.length )   // je ne comprends pas du tout pourquoi remettre cette partie, ce qu'elle fait, car elle ne fait que répéter ce qu'il y a au dessus, et sans l'algo ne fonctionne pas
		{
			t[i++] = t1[i1++];			
		}
 
		while( i2 < t2.length )
		{
			t[i++] = t2[i2++];
		}		
 
	}

merci pour votre lecture et vos réponses

[foetus]

En l'état, cette procédure ne pas être utilisée seule . Je pense qu'il faut la mettre dans une boucle.
De plus, je pense aussi que t1 et t2 correspond à 2 parties de t comme ceci: [<- t1 -><- t2 ->] t
Tous les nombres de t1 sont inférieurs à ceux de t2

Et donc, c'est pour cela:

• Que t[i++] ne déborde jamais: parce que tu dois parcourir à chaque fois le tableau t presque en entier
• Que tu es obligé de refaire 2 while après. Parce que tu as rempli soit t1 soit t2 en entier. Mais l'autre partie est incomplète. En effet le test du premier while est "si on a atteint la limite de l'une ou l'autre partie" i1 < t1.length && i2 < t2.length