fusionner deux tableaux triés ?

Version imprimable

06/06/2006, 20h12
sami_c

fusionner deux tableaux triés ?

Salut,
J'ai deux tableaux d'entiers T1 et T2, ils sont triés
Je voudrais un algorithme me permettant de fusionner T1 et T2 pour avoir un 3eme tableau T qui lui aussi est trié et ce sans avoir recours aux fonctions/procédures (si possible)
Merci :)
06/06/2006, 21h33
arnobidul

ben tu parcours les 2 tableaux en parallele et tu mets le plus petit a chaque fois dans ton tableau resultat de taille(T1) + taille(T2)...je vois pas trop le probleme..
06/06/2006, 21h55
sami_c

je ne vois pas trop comment tu veux faire, mais j'ai essayé cette solution (du moins une solution que je pense similaire) : le pb c'est qu'on aura des valeurs répétées plusieurs fois dans le nouveau tableau, et d'autres qui ne sont meme pas présentent dans le nouveau tableau !
Et meme si la méthode marche, je ne vois pas où a-t-on profité du fait que T1 et T2 sont triés ! Je pense que l'algo doit en tenir compte.
Bref stp essaie de détailler ta proposition sur papier et de faire un petit exemple
06/06/2006, 22h27
arnobidul

T1 : [1 3 6 7 9]

T2 : [2 3 4 6 9 10]

Tres : []

iteration1 : Tres : [1]
iteration2 : Tres : [1 2]
iteration3 : Tres : [1 2 3]
iteration4 : Tres : [1 2 3 3]
...
Tres : [1 2 3 3 4 6 6 7 9 9 10]

Tu profites quand meme en quelque sorte du tri initial, pour les doublons il reste pas grand chose a faire pour les virer si tu veux (quand tu compares les valeurs à l'endroit de tes iterateurs, si elles sont egales tu incrementes tes 2 iterateurs sinon un seul).

Bonjour,

Arno a donné la bonne méthode :
Supposant t1 et t2 en ordre croissant, le code devrait ressembler à ceci.

Code:

1
2
3
4
5
6
7
8
9
i1:=0 ; //  index dans t1
i2:=0 ; //  index dans t2
i :=0 ; //  index dans t
while (i1<high(t1)) or (i2<high(t2) do begin
   if (i2>high(t2) or ((i1<=high(t1)) and (t1[i1]<t2[i2]))  
     then begin t[i]:=t1[i1] ; i1:=i1+1 ; end ;
     else begin t[i]:=t2[i2] ; i2:=i2+1 ; end ;
   i:=i+1 ;
   end ;

08/06/2006, 09h57
sami_c

je vais tester ... mais est-ce que ça gère les doublons ? sachant qu'on ne doit PAS supprimer les doublons !
08/06/2006, 10h20
Graffito

Salut,

Les doublons sont conservés.
Pour les éliminer, il faudrait par exemple comparer t[i] avec t[i-1].
08/06/2006, 11h06
panda31

Les arbres binaires seraient utiles pour cela non ? Bon, c'est sur, leur intérêt se sentirait plutôt sur des tableaux de grande taille mais la récursivité simplifierait la vue sur le programme à mon goût.
08/06/2006, 11h59
ToTo13

Bonjour,

Citation:

Envoyé par panda31

Les arbres binaires seraient utiles pour cela non ?

C'est un peu bourrin, alors que cela peut se faire de manière linéaire.

Cet exercice est un cas d'école classique et la solution proposé par graffito est la meilleure.
08/06/2006, 12h19
panda31

oki