Algorithme de fusion de deux tableaux


Aide

On considère que une nouvelle fonction copie qui copie un tableau dans un autre même si ils n'ont pas la même définition. L'en-tête de la fonction est :
 fonction copie(ref T1:tableau[1..N1] d'élément;
                   ref T2:tableau[1..N2] d'élément;
                   val indiceT1_1,indiceT1_2,indiceT2: entier):vide;
Le shéma de la fonction fusion est alors le suivant.
fonction fusion(ref T1:tableau[1..N1] d'entier;
                ref T2:tableau[1..N2] d'entier
                ):tableau[1..N1+N2] d'entier;
  var I1,I2,i:entier;
  var T:tableau[1..N1+N2]d'entier;
  début
    Initialiser I1,I2,i
    tant que I1≤N1 et I2≤N2 faire
       ......On compare tant qu'il reste des éléments dans T1 et T2 
    fintantque
    si I1≤N1 alors
     il n'y a plus d'éléments dans T2 :copier(..........)
    sinon
     il n'y a plus d'éléments dans T1 :copier(..........)
    finsi
    retourner(T)
  fin
finfonction

Algorithme de fusion

fonction fusion(ref T1:tableau[D1..N1] d'entier;
                ref T2:tableau[D2..N2] d'entier
                ):tableau[1..N1+N2-D1-D2+2] d'entier;
  var I1,I2,i:entier;
  var T:tableau[1..N1+N2-D1-D2+2]d'entier;
  début
    i=1;
    I1=D1;
    I2=D2;
    tant que I1≤N1 et I2≤N2 faire
      si T1[I1]≤T2[I2] alors
        T[i]=T1[I1];
        I1=I1+1;
      sinon
        T[i]=T2[I2];
        I2=I2+1;
      finsi
      i=i+1
    fintantque
    si I1≤N1 alors
     copier(T1,T,I1,N1,i)
    sinon
     copier(T2,T,I2,N2,i)
    finsi
    retourner(T)
  fin
finfonction

Algorithme de fusion pour des morceaux de tableaux

fonction fusion(ref T1:tableau[D1..N1] d'entier;
                ref T2:tableau[D2..N2] d'entier;
		val DT1,FT1,DT2,FT2:entier):
		tableau[1..FT1+FT2-DT1-DT2+2] d'entier;
  var I1,I2,i:entier;
  var T:tableau[1..FT1+FT2-DT1-DT2+2]d'entier;
  début
    i=1;
    I1=DT1;
    I2=DT2;
    tant que I1≤FT1 et I2≤FT2 faire
      si T1[I1]≤T2[I2] alors
        T[i]=T1[I1];
        I1=I1+1;
      sinon
        T[i]=T2[I2];
        I2=I2+1;
      finsi
      i=i+1
    fintantque
    si I1≤FT1 alors
     copier(T1,T,I1,FT1,i)
    sinon
     copier(T2,T,I2,FT2,i)
    finsi
    retourner(T)
  fin
finfonction