A partire da due sequenze ordinate, v1 e v2, si vuole realizzare una terza sequenza ordinata v3.
Esempi
v1 = (1,2,4,5)
v2 = ()
v3 = (1,2,4,5)
Se una due sequenze è vuota è sufficiente copiare gli elementi dell’altra.
v1 = (1,2,4,5)
v2 = (20,30,40,60)
v3 = (1,2,4,5,20,30,40,60)
Se tutti gli elementi di una sequenza sono minori di tutti gli elementi dell’altra è sufficiente copiarli nell’ordine.
v1 = (1,2,4,5,7,10)
v2 = (2,3,4,6)
v3 = (1,2,2,3,4,4,5,6,7,10)
In generale bisogna decidere caso per caso quale elemento copiare.
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 | |
| 2, 3, 4, 6 | 1 | |
| 2, 3, 4, 6 | 1, 2 | |
| 2, 3, 4, 6 | 1, 2, 2 | |
| 1, 2, 2, 3 | ||
| 1, 2, 2, 3, 4 | ||
| 1, 2, 2, 3, 4, 4 | ||
| 1, 2, 2, 3, 4, 4, 5 | ||
| 1, 2, 2, 3, 4, 4, 5, 6 | ||
| 1, 2, 2, 3, 4, 4, 5, 6, 7 | ||
| 1, 2, 2, 3, 4, 4, 5, 6, 7, 10 | ||
Codifica Pascal
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;
Fusione di sottosequenze ordinate
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
V = (1,2,4,5,7,10,2,3,4,6)
inf = 1, medio = 6, sup = 10
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
V = (1,2,4,5,7,10,2,3,4,6)
inf = 4, medio = 6, sup = 7
V' = (5,7,10)
V" = (2)
V = (1,2,4,2,5,7,10,3,4,6)
Codifica Pascal
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;