Fusione
Di due sequenze
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 | |
| 2, 4, 5, 7, 10 | 2, 3, 4, 6 | 1 |
| 4, 5, 7, 10 | 2, 3, 4, 6 | 1, 2 |
| 4, 5, 7, 10 | 3, 4, 6 | 1, 2, 2 |
| 4, 5, 7, 0 | 4, 6 | 1, 2, 2, 3 |
| 5, 7, 10 | 4, 6 | 1, 2, 2, 3, 4 |
| 5, 7,10 | 6 | 1, 2, 2, 3, 4, 4 |
| 7, 10 | 6 | 1, 2, 2, 3, 4, 4, 5 |
| 7, 10 | 1, 2, 2, 3, 4, 4, 5, 6 | |
| 10 | 1, 2, 2, 3, 4, 4, 5, 6, 7 | |
| 1, 2, 2, 3, 4, 4, 5, 6, 7, 10 |
Pseudocodice
FUNCTION merge(IN REALE v1[], IN REALE v2[]) : REALE[]
INIZIO
INTERO i1=0, n1=v1.QUANTI,
i2=0, n2=v2.QUANTI,
i3=0, n3=n1+n2
REALE v3[]=NUOVO REALE[n3]
MENTRE(i1 < n1 AND i2 < n2)
INIZIO
SE(v1[i1] <= v2[i2]) ALLORA
INIZIO
v3[i3]=v1[i1]
i1=i1+1
FINE
ALTRIMENTI
INIZIO
v3[i3]=v2[i2]
i2=i2+1
FINE
i3=i3+1
FINE
MENTRE(i1 < n1)
INIZIO
v3[i3]=v1[i1]
i1=i1+1
i3=i3+1
FINE
MENTRE(i2 < n2)
INIZIO
v3[i3]=v2[i2]
i2=i2+1
i3=i3+1
FINE
merge=v3
FINE
INIZIO
INTERO i1=0, n1=v1.QUANTI,
i2=0, n2=v2.QUANTI,
i3=0, n3=n1+n2
REALE v3[]=NUOVO REALE[n3]
MENTRE(i1 < n1 AND i2 < n2)
INIZIO
SE(v1[i1] <= v2[i2]) ALLORA
INIZIO
v3[i3]=v1[i1]
i1=i1+1
FINE
ALTRIMENTI
INIZIO
v3[i3]=v2[i2]
i2=i2+1
FINE
i3=i3+1
FINE
MENTRE(i1 < n1)
INIZIO
v3[i3]=v1[i1]
i1=i1+1
i3=i3+1
FINE
MENTRE(i2 < n2)
INIZIO
v3[i3]=v2[i2]
i2=i2+1
i3=i3+1
FINE
merge=v3
FINE
