Discussion :

[Mailgifson]

Je dois faire un programme en C de tri d'un tableau d'entier par fusion mais je ne comprend comment c possible de le faire. Si quelqu'un a un exemple ou une source, ça serait sympa !

Merci

[Shadow Blade]

Cela doit fonctionnner :


/* TRI DICHOTOMIQUE */

#include "STDIO.H"

#define COPIER(A,i,B,j) {(B)[(j)++]=(A)[(i)++] ;}
#define TAILLE 50
#define FICHIER "tabl.txt"

void fusionner(int R[], int M, int S[], int N, int T[])
{
int i = 0, j = 0, k = 0;

while (i<M && j<N) {

if (R[i]<S[j])
COPIER(R,i,T,k)
else
COPIER(S,j,T,k)
}

while (i<M) COPIER(R,i,T,k)
while (j<N) COPIER(S,j,T,k)
}

void copierTableau(int A[], int i, int j, int B[])
{
int k=0;
while (i<j) COPIER(A,i,B,k)
}

void triParFusion(int T[], int N)
{
int R[TAILLE], S[TAILLE];
if (N<=1)
return;
copierTableau(T,0,N/2,R);
copierTableau(T,N/2,N,S);
triParFusion(R,N/2);
triParFusion(S,(N-N/2));
fusionner(R,N/2,S,(N-N/2),T);
}


main()
{
FILE *FLUX_IN, *FLUX_OUT;
int i=0, n;
int tab[TAILLE];

FLUX_IN = fopen(FICHIER,"r");

if ( FLUX_IN == NULL ) {
printf("Impossible d'ouvrir %s", FLUX_IN);
fgetc(stdin);
return -1;
}

while( feof(FLUX_IN) == 0 ) {
fscanf(FLUX_IN, "%d", &tab[i]);
i++;
}

fclose(FLUX_IN);
n = i;

printf("\nAvant le tri\n");
for(i=0; i<n; i++)
fprintf(stdout, "%d ", tab[i]);

triParFusion(tab, n);

printf("\nApres le tri par fusion !\n" );
for(i=0; i<n; i++)
fprintf(stdout, "%d ", tab[i]);


fgetc(stdin);
return 0;
}

[ken_survivant]

Salut,

Voici la méthode en gros... Je n'ai malheureusement plus le code...

Donc par exemple, tu as un tableau de n données que tu souhaiterais trier !

1. Eclate ton tableau dans deux tableaux ou deux listes chainées (je préfère la seconde mais bon)

2. Tu tries chaque liste (il suffit de jouer avec les pointeurs de ta liste)

3. Tu les fusionnes (chaque liste étant triée -> pas de prob)

Voilà, ce n'est pas dur et en plus si tu connais la récursivité, c'est plus court !

Courage !

Ken

[lefort]

Pourqoi pas utiliser le tri rapide ? Qui est plus optimal que le trie 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
 
void echange(typetab tab,int i,int j)
{
      composante tampon=tab[i];
      tab[i]=tab[j];
      tab[j]=tampon;
}
 
void trirapid(typetab tab,int G,int D)
{
      int g,d;
      composante val;
      if(D<=G)
            return();
      val=tab[D];
      g=G-1;
      d=D; 
      do
      {
            while((tab[++g]<val));
            while((tab[--d]>val)&&(d>G));
            if(g<d)
                  echange(tab,g,d);
      }
      while(g<d);
      echange(tab,g,D)
      trirapide(tab,G,g-1);
      trirapide(tab,g+1,D);
}

Salut !

[Shadow Blade]

Je connaissais pas le tri rapide !
Je vais tester cela !

@+ !

[ken_survivant]

REMARQUE IMPORTANTE

Le tri rapide -> le nom est bien mais faut qd même regarder la complexité !

Dans le pire des cas, cet algo s'exécute en O(n²) ce qui n'est pas très rapide.

En fait c'est la complexité en moyenne qui est bonne -> O(n log2 n)...

Voilà, bonne journée

Ken