Discussion :

[Delnir]

Bonsoir,
je m'entraine un peut sur les tries et compléxité et la je bloque sur le trie fusion.
Le tableau ne change pas, j'ai l'impression que la fusion ne se fait pas

pouvez-vous m'indiquer mes erreurs?

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
 
#include <stdlib.h>
#include <stdio.h>
 
#define MAX 4
 
void affiche(int *tab){
  int i;
  for(i=0;i<MAX;i++)
    printf("%d ",tab[i]);
}
 
void fusion(int *tab,int debut,int milieu,int fin){
  int tab1[milieu],tab2[milieu],i,i1=debut-1,i2=debut-1;
  for(i=0;i<milieu;i++){
    tab1[i]=tab[i];
    tab2[i]=tab[milieu+1+i];
  }
 
  for(i=0;(i1<milieu && i2<milieu);i++){
    if(tab1[i1]>tab2[i2])
      tab[i]=tab2[i2++];
    else
      tab[i]=tab1[i1++];
  }
  if(i<fin){
    while(i1<milieu)
      tab[i++]=tab1[i1++];
    while(i2<milieu)
      tab[i++]=tab2[i2++];
  }
}
 
void trieFusion(int *tab,int debut,int fin){
  if(debut>fin){
    trieFusion(tab,debut,((fin+debut)/2));
    trieFusion(tab,((fin+debut)/2)+1,fin);
    fusion(tab,debut,(fin+debut)/2,fin);
  }
}
 
int main(void){
  int tab[]={3,2,1,4};
  printf("Avant trie:\n");
  affiche(tab);
  printf("\n");
  trieFusion(tab,1,MAX);
  printf("Apres trie:\n");
  affiche(tab);
  printf("\n");
  return 0;
}

Merci d'avance pour votre aide.

[Médinoc]

Le tri-fusion sur place, c'est très compliqué et algorithmiquement ça ne vaut pas le coup.

Le mieux est de travailler avec deux tableaux de taille identique, en agissant à chaque fois "d'un tableau à l'autre".

[Pouet_forever]

Son tri ne se fait pas en place, il utilise le C99 tout simplement :

Code :

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

int tab1[milieu],tab2[milieu]

Ta condition ne sera jamais vraie : if(debut>fin)
Debut sera toujours inférieur à fin (enfin dans un usage normal).

Dans ta fonction trieFusion (au passage ça s'écrit 'tri' sans 'e') tu calcules plusieurs fois (fin+debut)/2, tu pourrais utiliser une variable pour ne pas le calculer plusieurs fois.

Il faut que tu changes tes indices, le premier élément du tableau est 0 et pas 1. Il est plus simple de passer 0 plutôt que de soustraire tout le temps 1.

Ta fonction à l'air à peu près correcte, mais ne fonctionnera que sur des tableau avec une taille en puissance de 2 (2, 4, 8, etc.) ; sur des tableaux quelconques ça ne fonctionnera pas (à cause de la division).

[Delnir]

merci pour votre aide, sa marche

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
 
void fusion(int *tab,int debut,int milieu,int fin){
  int tab1[milieu],tab2[fin-milieu],i,posT1=0,posT2=0,tailleTab2=fin-milieu;
 
  for(i=0;i<milieu;i++){
     tab1[i]=tab[i];
     if(i<tailleTab2)
       tab2[i]=tab[milieu+i];
  }
 
  for(i=0;(posT1<milieu && posT2<tailleTab2);i++){
    if(tab1[posT1]>tab2[posT2])
      tab[i]=tab2[posT2++];
    else
      tab[i]=tab1[posT1++];
  }
 
  for(;posT1<milieu;posT1++,i++)
    tab[i]=tab1[posT1];
 
  for(;posT2<tailleTab2;posT2++,i++)
    tab[i]=tab2[posT2];
}
 
void triFusion(int *tab,int debut,int fin){
  int i,milieu;
  if(debut<fin){
    milieu=((fin+debut)/2);
    triFusion(tab,debut,milieu);
    triFusion(tab,milieu+1,fin);
    fusion(tab,debut,milieu,fin);
  }
}