|
e-ΜΑΘΗΜΑΤΑ |
|
Λύσεις ασκήσεων από θέματα Πανελλαδικών εξετάσεων |
Αλγόριθμος Συγχώνευση
! Συγχώνευση
! Η συγχώνευση (merging) είναι μία ακόμη βασική λειτουργία των δομών δεδομένων.
! Ειδικότερα, έχει μελετηθεί το πρόβλημα της συγχώνευσης ενός αριθμού (δύο,
! τριών ή και περισσοτέρων) ταξινομημένων πινάκων.
! Στη συνέχεια δίνεται ένας απλός αλγόριθμος συγχώνευσης δύο ταξινομημένων
! πινάκων σε ένα τρίτο ταξινομημένο πίνακα.
!
! Θεωρείται ότι στην είσοδο του αλγορίθμου συγχώνευσης δίνονται δύο ταξινομημένοι
! πίνακες x και y, μεγέθους n και m στοιχείων αντίστοιχα, ενώ στην έξοδο
! προκύπτει ένας τρίτος πίνακας z με n+m ταξινομημένα στοιχεία κατά την ίδια φορά.
! Πιο ειδικά, οι μεταβλητές i, j και k είναι δείκτες για την κίνηση μέσα στους
! πίνακες x, y και z.
! Η μέθοδος προχωρά ως εξής:
! Το μικρότερο στοιχείο από τους πίνακες x και y τοποθετείται στον πίνακα z
! με ταυτόχρονη αύξηση του αντίστοιχου δείκτη.
! Η διαδικασία αυτή επαναλαμβάνεται μέχρις ότου τελειώσουν τα στοιχεία του
! ενός πίνακα.
! Ύστερα τα υπόλοιπα στοιχεία του άλλου πίνακα μεταφέρονται στον πίνακα z.
Δεδομένα // n, m, x, y //
i <- 1
j <- 1
k <- 1
Όσο i ≤ n και j ≤ m επανάλαβε
Αν x[i] < y[j] τότε
z[k] <- x[i]
i <- i + 1
αλλιώς
z[k] <- y[j]
j <- j + 1
Τέλος_αν
k <- k + 1
Τέλος_επανάληψης
Αν i > n τότε
Για t από j μέχρι m
z[k] <- y[t]
k <- k + 1
Τέλος_επανάληψης
αλλιώς
Για t από i μέχρι n
z[k] <- x[t]
k <- k + 1
Τέλος_επανάληψης
Τέλος_αν
Αποτελέσματα // z //
Τέλος Συγχώνευση
|
|
|
|
