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) - v1=(1, 2, 4, 5)
v2=(20, 30, 40, 60)
v3=(1, 2, 4, 5, 20, 30, 40, 60) - 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
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)
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
inf=4, medio=6, sup=7
allora
V' = (5, 7, 10)
V'' = (2)
V = (1, 2, 4, 2, 5, 7, 10, 3, 4, 6)
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;