Fusione di sequenze

di

A partire da due sequenze ordinate, v1 e v2, si vuole realizzare una terza sequenza ordinata v3.

Esempi

  1. v1=(1, 2, 4, 5)
    v2=()
    v3=(1, 2, 4, 5)
  2. v1=(1, 2, 4, 5)
    v2=(20, 30, 40, 60)
    v3=(1, 2, 4, 5, 20, 30, 40, 60)
  3. v1=(1, 2, 4, 5, 7, 10)
    v2=(2, 3, 4, 6)
    v3=(1, 2, 2, 3, 4, 4, 5, 6, 7, 10)

Algoritmo

Una scansione delle due sequenze sceglie, a ogni passo, l’elemento da copiare nella terza sequenza.
È sufficiente confrontare i primi elementi perché…

Esempio

v1 v2 v3
1, 2, 4, 5, 7, 10 2, 3, 4, 6 1
2, 4, 5, 7, 10 2, 3, 4, 6 1, 2
4, 5, 7, 10 2, 3, 4, 6 1, 2, 2
4, 5, 7, 10 3, 4, 6 1, 2, 2, 3
4, 5, 7, 0 4, 6 1, 2, 2, 3, 4
5, 7, 10 4, 6 1, 2, 2, 3, 4, 4
5, 7,10 6 1, 2, 2, 3, 4, 4, 5
7, 10 6 1, 2, 2, 3, 4, 4, 5, 6
7, 10 1, 2, 2, 3, 4, 4, 5, 6, 7
10 1, 2, 2, 3, 4, 4, 5, 6, 7, 10 
Procedure MERGE(     V1: Vettore;     L1: Integer;
                     V2: Vettore;     L2: Integer;
                 Var V3: Vettore; Var L3: Integer);
Var
   I, J, K: Integer;
Begin
   I:=1;
   J:=1;
   K:=1;
   While(I <= L1) And (J <= L2) Do
      Begin
         If(V1[I] <= V2[J]) Then
            Begin
               V3[K]:=V1[I];
               Inc(I);
            End
         Else
            Begin
               V3[K]:=V2[J];
               Inc(J);
            End;
         Inc(K);
      End;
   While(I <= L1) Do
      Begin
         V3[K]:=V1[I];
         Inc(I);
         Inc(K);
      End;
   While(J <= L2) Do
      Begin
         V3[K]:=V2[J];
         Inc(J);
         Inc(K);
      End;
   L3:=K-1;
End;

Sottosequenze

Supponiamo che l’array V contenga due sottoarray adiacenti ordinati

  • V’, da inf a medio
  • V”, da medio+1 a sup

e che l’obbiettivo sia ordinare l’array da inf a sup.

Esempio 1

Con

V = (1, 2, 4, 5, 7, 10, 2, 3, 4, 6)
inf=1, medio=6, sup=10

allora

V' = (1, 2, 4, 5, 7, 10)
V'' = (2, 3, 4, 6)
V = (1, 2, 2, 3, 4, 4, 5, 6, 7, 10)

Esempio 2

Con

V = (1, 2, 4, 5, 7, 10, 2, 3, 4, 6)
inf=4, medio=6, sup=7

allora

V' = (5, 7, 10)
V'' = (2)
V = (1, 2, 4, 2, 5, 7, 10, 3, 4, 6)

Si può adattare il codice precedente in modo che i dati siano copiati, in ordine, su un array temporaneo VTemp e poi ricopiati su V, da inf a sup.
Procedure MERGE(Var V: Vettore; Inf, Medio, Sup: Integer);
Var
   I, J, K: Integer;
   VTemp  : Vettore;
Begin
   I:=Inf;
   J:=Medio+1;
   K:=Inf;
   While(I <= Medio) And (J <= Sup) Do
      Begin
         If(V[I] <= V[J]) Then
            Begin
               VTemp[K]:=V[I];
               Inc(I);
            End
         Else
            Begin
               VTemp[K]:=V[J];
               Inc(J);
            End;
         Inc(K);
      End;
   While(I <= Medio) Do
      Begin
         VTemp[K]:=V[I];
         Inc(I);
         Inc(K);
      End;
   While(J <= Sup) Do
      Begin
         VTemp[K]:=V[J];
         Inc(J);
         Inc(K);
      End;
   For I:=Inf To Sup Do
      V[I]:=VTemp[I];
End;