Παράδειγμα 3 Κεφάλαιο 9, Συγχώνευση Πινάκων

Δίνονται δύο ταξινομημένοι κατά αύξουσα σειρά μονοδιάστατοι πίνακες, ακεραίων αριθμών. Να γραφεί πρόγραμμα το οποίο να συγχωνεύει τους δύο πίνακες σε έναν τρίτο ο οποίος να είναι επίσης ταξινομημένος κατά αύξουσα σειρά. Οι δύο αρχικοί πίνακες δεν μπορούν να περιέχουν περισσότερα από 100 στοιχεία ο καθένας.

Η συγχώνευση είναι μία βασική λειτουργία των πινάκων και γενικότερα των δομών δεδομένων. Στη συνέχεια δίνεται ένας πολύ απλός αλγόριθμος συγχώνευσης δύο ταξινομημένων πινάκων σε έναν τρίτο ταξινομημένο πίνακα.

Θεωρείται ότι στην είσοδο του αλγορίθμου συγχώνευσης δίνονται δύο ταξινομημένοι, κατά αύξουσα σειρά, πίνακες Α και Β, μεγέθους Ν και Μ στοιχείων αντίστοιχα, ενώ στην έξοδο προκύπτει ένας τρίτος πίνακας Γ με Ν+Μ ταξινομημένα στοιχεία επίσης κατά αύξουσα σειρά.

Στο πρόγραμμα Συγχώνευση που ακολουθεί οι μεταβλητές i, j και k είναι δείκτες για την κίνηση μέσα στους πίνακες Α, Β και Γ. Η μέθοδος προχωρεί ως εξής: Το μικρότερο στοιχείο από τους πίνακες Α και Β τοποθετείται στον πίνακα Γ με ταυτόχρονη αύξηση του αντίστοιχου δείκτη. Η διαδικασία αυτή επαναλαμβάνεται μέχρις ότου τελειώσουν τα στοιχεία του ενός πίνακα.

Στη συνέχεια τα υπόλοιπα στοιχεία του άλλου πίνακα μεταφέρονται στον πίνακα Γ.

ΠΡΟΓΡΑΜΜΑ Συγχώνευση 
ΜΕΤΑΒΛΗΤΕΣ 
ΑΚΕΡΑΙΕΣ: Α[100], B[100], Γ[200], I, J, Κ, Ν, Μ, Λ 
! Α και Β αρχικοί πίνακες 
! Γ τελικός πίνακας 
ΑΡΧΗ 

! Διάβασε τα δεδομένα 
ΓΡΑΨΕ 'Δώσε το πλήθος των στοιχείων του πίνακα Α (<100)' 
ΔΙΑΒΑΣΕ Ν 
ΓΙΑ I ΑΠΟ 1 ΜΕΧΡΙ Ν 
    ΔΙΑΒΑΣΕ Α[I] 
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ 'Δώσε το πλήθος των στοιχείων του πίνακα Β(<100)'
ΔΙΑΒΑΣΕ Μ 
ΓΙΑ I ΑΠΟ 1 ΜΕΧΡΙ Μ 
    ΔΙΑΒΑΣΕ B[I] 
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ 

! Συγχώνευση πινάκων
! I είναι ο δείκτης για τον πίνακα Α 
! J είναι ο δείκτης για τον πίνακα Β 
! Κ είναι ο δείκτης για τον πίνακα Γ 
I <-- 1 
J <-- 1 
Κ <-- 1 
ΟΣΟ I <= Ν ΚΑΙ J <= Μ ΕΠΑΝΑΛΑΒΕ 
! Όσο και τα δύο έχουν στοιχεία 
    ΑΝ Α[I] < B[J] ΤΟΤΕ 
       Γ[Κ] <-- Α[I] 
       Κ <-- Κ+1 
       I <-- I+1 
    ΑΛΛΙΩΣ 
       Γ[Κ] <-- B[J] 
       Κ <-- Κ+1 
       J <-- J +1 
    ΤΕΛΟΣ_ΑΝ 
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ 

! Μεταφορά των υπολοίπων στοιχείων του Α ή του Β 
ΑΝ I > Ν ΤΟΤΕ 
   ΓΙΑ Λ ΑΠΟ Κ ΜΕΧΡΙ Ν+Μ 
       Γ[Λ] <-- B[J] 
       J <-- J +1 
   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ 
ΑΛΛΙΩΣ 
   ΓΙΑ Λ ΑΠΟ Κ ΜΕΧΡΙ Ν+Μ 
       Γ[Λ] <-- Α[I] 
       I <-- I+1 
   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ 
ΤΕΛΟΣ_ΑΝ

! Εκτύπωση τελικού πίνακα 
ΓΙΑ Λ ΑΠΟ 1 ΜΕΧΡΙ Ν+Μ 
    ΓΡΑΨΕ Γ[Λ] 
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ 
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ