Fusione, un algoritmo.

Con riferimento al post precedente, un algoritmo che realizzi la fusione fra due strutture dati potrebbe essere il seguente:

Supponiamo che le strutture S1 e S2 siano due file e che si voglia scrivere in output un nuovo file contenente l'unione dei due input.

L'idea di base è di memorizzare la chiave di fusione in una variabile "key1" per S1 e "key2" per S2 e lavorare sulle relazioni logiche che possono crearsi fra queste due variabili.

1. Se key1 è minore di key2, S1 andrà in output e un nuovo valore di S1 sarà letto;
2. Se key1 è maggiore di key2, S2 andrà in output e un nuovo valore di S2 sarà letto;
3. Se key1 è uguale a key2, uno fra S1 e S2 andrà in output e un nuovo valore sia di S1 che di S2 sarà letto;

Questa serie di confronti andrà avanti fino a quando tutte le letture saranno completate.

Per gestire il caso, frequente, di file di grandezza diversa si avrà cura, nel caso uno dei due file termini prima dell'altro, di porre la chiave corrispondente ad un valore "tappo" (Tipicamente in COBOL si usa HIGH-VALUE).

In questo modo una delle due condizioni 1 e 2 sarà sempre verificata provocando lo scarico dell'altro file in output.

L'algoritmo precedente può essere espresso in pseudo-codifica nel modo seguente:

START

    OPEN S1, S2,OUT;

    READ S1 IN KEY1 AT END KEY1=HV;

    READ S2 IN KEY2 AT END KEY2=HV;

    PERFORM UNTIL KEY1=HV AND KEY2=HV

        IF KEY1 < KEY2 THEN

             WRITE OUT FROM S1;

             READ S1 IN KEY1 AT END KEY1=HV;

        ELSE

             IF KEY1 > KEY2 THEN

                 WRITE OUT FROM S2;

                 READ S2 IN KEY2 AT END KEY2=HV;         

             ELSE

                  WRITE OUT FROM S1;

                  READ S1 IN KEY1 AT END KEY1=HV;

                  READ S2 IN KEY2 AT END KEY2=HV;

             END-IF;

       END-IF;

    END-PERFORM;

    CLOSE S1,S2,OUT

END