Tri par fusion d'un tableau

Version imprimable

23/11/2002, 11h42
Mailgifson

Tri par fusion d'un tableau

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
23/11/2002, 17h39
Shadow Blade

Cela doit fonctionnner :D :

/* 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;
}
24/11/2002, 13h04
ken_survivant

Tri par fusion

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

Pourqoi pas utiliser le tri rapide ? Qui est plus optimal que le trie fusion !!!

Code:

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 !

29/11/2002, 18h28
Shadow Blade

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

@+ !
12/12/2002, 14h53
ken_survivant

Tri rapide !!!

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 :lol:

Ken