Trier deux tableaux et les fusionner

Version imprimable

bonjour a tous :)

j'ai réalisé un programme qui permet de saisir , remplir et trier deux tableaux puis fissionner ces deux tableaux en gardant le trie dans un 3ème tableau .

mon programme se fonctionne mais mon problème lorsque s'affiche le 3éme tableau du fusion je trouve qu'il n'est pas trié .

j'ai essayé plusieurs fois pour le corriger mais toujours le même problème ,

donc j'ai besoin de vos aide mes ami(e)s.

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
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
89
90
91
92
93
#include <stdio.h>
#include <stdlib.h>
 
 
 
void tri(int tabl[], int n)
{
    int c,j;
 
    for(j=0;j<n-1;j++) {
        if(tabl[j]>tabl[j+1]) {
 
            c=tabl[j];
 
            tabl[j]=tabl[j+1];
 
            tabl[j+1]=c;
        }
    }
 
}
 
void remplissage(int s, int tab[50], int tab1[50]){
 
    int i,j;
 
    printf("remplir le 1ere tableau \n");
    for(i=0;i<s;i++){
        scanf("%d",&tab[i]);
    }
 
 
    printf("remplir le 2eme tableau \n");
    for(j=0;j<s;j++){
        scanf("%d",&tab1[j]);
    }
 
}
 
 
void main(){
 
    int j=0,i=0,s=0,n,f,x;
 
    int t[50],t1[50];
 
    printf("donner la taille de 2 tableaux \n");
    scanf("%d",&n);
 
    remplissage(n,t,t1);
 
 
    tri(t,n);
 
    tri(t1,n);
 
    //affichage de trie de 1ére et 2éme tableaux;
    printf("le 1er tableau trie.\n");
    for(i=0;i<n;i++) {
        printf("%5d\n",t[i]);
    }
 
    printf("le 2eme tableau trie.\n");
    for(i=0;i<n;i++) {
        printf("%5d\n",t1[i]);
    }
 
 
    //fusion du 2 tableaux
    f=n+n;
 
    int fus[f];
 
    for(i=0;i<n;i++) {
        fus[i]=t[i];
    }
    for(i=0;i<n;i++) {
        fus[i+n]=t1[i];
    }
    tri(fus,f);
 
 
    printf("Tableau fusionne\n");
 
    for(i=0;i<f;i++) {
        printf("%5d",fus[i]);
    }
    printf("\n");
 
 
    return 0;
 
}

Merci

28/10/2014, 12h38
Médinoc

Ta fonction de tri n'est pas bonne: Tous les tris "naïfs" doivent utiliser deux boucles for, c'est ce qui leur donne leur complexité en O(n²).

Oups! Mon message est venu avec du retard. :P Je le laisse quand même.
Le problème vient de la fonction de tri. Il te faut utiliser deux boucles for au lieu d'une seule. La version correcte est donc
Code:

1 2 3 4 5 6 7 8 9 for (i = 0; i < n - 1; i++) for (j = 0; j < n - 1 - i; j++) { if(t[j]>t[j+1]) { c=t[j]; t[j]=t[j+1]; t[j+1]=c; } }
Il existe, comme l'a dit Medinoc, des algorithmes de tri bien meilleurs que celui-ci. Fais un tour dans les FAQs Algo et C pour plus d'informations.

28/10/2014, 14h06
Médinoc

Le tri à bulle a quand même des mérites; notamment il est stable, in-place et sans demande additionnelle de mémoire.
Le tri par sélection et le QuickSort ne sont pas stables, et si je me souviens bien le tri fusion n'est vraiment plus rapide que s'il n'est pas in-place.

Bonjour
Citation:
Envoyé par syrine01
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 void remplissage(int s, int tab[50], int tab1[50]){ int i,j; printf("remplir le 1ere tableau \n"); for(i=0;i<s;i++){ scanf("%d",&tab[i]); } printf("remplir le 2eme tableau \n"); for(j=0;j<s;j++){ scanf("%d",&tab1[j]); } }
Une fonction de remplissage qui répète deux-fois les mêmes instructions ; en utilisant en plus deux variables "i" et "j" (alors qu'une seule variable suffit vu que quand "j" est utilisé, "i" ne l'est plus) !!!
Mais surtout il ne t'est pas venu à l'esprit d'écrire une fonction de remplissage qui remplit un tableau puis de l'appeler deux fois en lui passant en paramètre le tableau à remplir ???

Citation:

Envoyé par syrine01

Code:

void main()

main est de type int
Citation:
Envoyé par syrine01
Code:

1 2 3 4 5 6 7 8 9 10 11 12 //fusion du 2 tableaux f=n+n; int fus[f]; for(i=0;i<n;i++) { fus[i]=t[i]; } for(i=0;i<n;i++) { fus[i+n]=t1[i]; } tri(fus,f);
C'est pas ça une fusion. Accessoirement une seule boucle aurait suffit mais surtout c'est idiot de trier les deux tableaux si tu retrie en final le tableau fusionné. Autant remplir le tableau fusionné à partir des deux tableaux non triés. Ca te donnera le même résultat mais avec moins de travail.

Donc sinon une fusion de deux (ou n) tableaux triés se fait de la façon suivante: tu prends un élément dans chaque tableau et tant que l'élément du tableau X est plus petit que l'élément du tableau Y tu l'écris dans le 3° et tu passes à l'élément suivant du tableau X. Quand l'inégalité bascule c'est alors l'élément du tableau Y que tu écris dans le 3° et c'est le tableau Y qui passe au suivant. Et etc etc jusqu'à ce que les deux tableaux aient été traités. Avec ça, pas besoin de retrier le 3°...