Discussion :

[sami_c]

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

[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..

[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

[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).

[Graffito]

Bonjour,

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

Code :

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

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 ;

[sami_c]

je vais tester ... mais est-ce que ça gère les doublons ? sachant qu'on ne doit PAS supprimer les doublons !

[Graffito]

Salut,

Les doublons sont conservés.
Pour les éliminer, il faudrait par exemple comparer t[i] avec t[i-1].

[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.

[ToTo13]

Bonjour,

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.

[panda31]

oki