Fusione di sequenze

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

Codifica Pascal

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)

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.