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

[Mckinl3y]

En effet cette procédure n'est pas utilisée seule, j'ai la méthode tri fusion en plus, qui est la suivante :

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
	static void Tri_fusion(int t[])
	{
		if( t.length > 1 )
		{
			int milieu = (int)(t.length / 2);			
 
			int tab1[] = new int[milieu];		
			int tab2[] = new int[t.length - milieu];
 
			for(int i = 0, k =0; i < milieu; i++, k++)
			{
				tab1[k] = t[i];					
			}
 
			for(int i = milieu, k = 0; i < t.length; i++, k++)
			{
				tab2[k] = t[i];	
			}
 
			Tri_fusion(tab1);
			Tri_fusion(tab2);
 
			fusion(t, tab1, tab2);	
		}
		}

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

je pense plus que t1 et t2 sont deux sous ensembles différents qu'il faut trier et ajouter à un t vide ? ( aux vues de la fonction tri_fusion)

Que t[i++] ne déborde jamais: parce que tu dois parcourir à chaque fois le tableau t en entier

en réalité, c'est l'expression t[i++] que je ne comprends absolument pas, ce qu'elle signifie.

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

l'idée n'est elle pas justemment de remplir le t au lieu des t1 et t2. Le premier while n'est il pas plutot "TANT QUE l'on est pas arrivés à la fin des deux tableau on refait le test" ?
Le test prend bien une valeur de t1 et t2, les compare, si t1 < t2 il la place en premier dans t et avance le curseur au niveau de t1.
je ne comprends pas pourquoi cela ne suffit pas ?

merci pour votre temps

[foetus]

Cet algo complètement pourri

On fait 2 new à chaque appel: certains membres ici vont faire une crise cardiaque
Et en plus, sans les delete[].


De plus, j'ai plus l'impression d'avoir affaire à un tri rapide: on divise par 2 notre tableau (ainsi le pivot c'est le milieu).
On lance la récursion sur les 2 parties.
Et lorsqu'on a plus qu'un seul élément on sait le trier avec un autre

[Mckinl3y]

Ah d'accord, ma prof m'a donné ça sans trop d'explications, donc j'esseyais de comprendre.
Il vaut donc mieux que je parte sur autre chose ?

l'idée du tri fusion n'est elle pas de travailler de façon dichotomique en divisant chaque fois le tableau pour arriver à des éléments uniques que l'on trie au fur et à mesure .

type :
748216
748 216
7 48 2 16
7 4 8 2 1 6
47 28 16
2478 16
124678
?

Merci

[foetus]

En regardant Wiki, cela semble être cela

On prend un tableau t, on le découpe en 2. À la descente, t devient soit t1 soit t2.
C'est la partie:

Code :

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

1
2
			Tri_fusion(tab1);
			Tri_fusion(tab2);

Et à la remontée, on va recopier en triant t1 et t2
C'est la partie: fusion(t, tab1, tab2);.

Et justement le t[i++] permet de recopier les 2 parties t1 et t2 dans t.
Regardes l'exemple de Wiki: t1: 9, 82 - t2: 10 -> t à la fin: 9, 10, 82
Et comme je le soupçonnais , il n'y a pas de débordement parce que la longueur de t1 plus celle de t2 est égale à la longueur de t

Et donc les 2 while servent à recopier la partie qui n'a été recopiée en entier
Reprends l'exemple t1: 9, 82 - t2: 10

Étape 1: tu prends 9 puisque 9 < 10 -> t: 9
Étape 2: tu prends 10 puisque 10 < 82 -> t: 9, 10
Étape 3: tu as fini ...
Étape 3.1: ... enfin presque est-ce qu'il reste des valeurs dans t1?: non
Étape 3.2: ... enfin presque est-ce qu'il reste des valeurs dans t2?: oui, 82 -> t: 9, 10, 82

[Mckinl3y]

Je te remercie pour ta réponse.

aurais tu une traduction littérale de

Code :

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

t[i++] = t1[i1++];

?

Merci votre temps par avance

[foetus]

Sur quoi tu bloques : déroule l'algo pour comprendre c'est trivial

i, i1 et i2 -> ce sont 3 index de tableaux respectivement de t, t1 et t2
i++ -> on incrément de 1, mais on fait l'incrémentation après coup. ++i c'est avant
t[x] -> on prend la valeur du tableau à l'indice x

Reprends l'exemple t1: [9, 82] et t2: [10], t est vide: []

i, i1 et i2 vaut tous 0 int i = 0, i1 = 0, i2 = 0;.

if( t1[i1] < t2[i2] ) -> t1[0] == 9 et t2[0] == 10 ->
t[i++] = t1[i1++]; -> On prend 9 (t1[0], (i1 == 0)) et on met la valeur dans la case 0 de t (i == 0). et on incrémente après l'affection i et i1.

Donc i, i1 et i2 vaut 1, 1, et 0, et t: [9]

Et ainsi de suite

[Mckinl3y]

Merci beaucoup, l'ampoule vient de s'allumer !!

c'était vraiment juste le i++ qui bloquait, le côté incrémentation APRES, c'est une subtilité que je n'avais pas encore lu, je débute juste.

J'avais un doute car j'avais testé à la place :

Code :

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

1
2
3
4
5
{
t[i] = t2[i2];
 i++;
 i2++;
}

sans succès

Bref merci pour votre patience !