Θέμα: Συγχώνευση κ να προκύψει ταξινομημένος πίνακας

[Νίκος Αδαμόπουλος]

Εναλλακτικός αλγόριθμος:

Αλγόριθμος Συγχώνευση
Δεδομένα // Α, Β, Ν, Μ //  ! Ν είναι το πλήθος των στοιχείων του πίνακα Α (<=100) και Μ το πλήθος των στοιχείων του πίνακα Β (<=100)

Ι <- 1
J <- 1
Για Κ από 1 μέχρι Ν+Μ
  Αν Ι <= Ν και J <= Μ τότε
     Αν Α[Ι] < Β[J] τότε
        Γ[Κ] <- Α[Ι]
        Ι <- Ι+1
     αλλιώς
        Γ[Κ] <- Β[J]
        J <- J +1
     Τέλος_αν
  αλλιώς_αν Ι <= Ν τότε
     Γ[Κ] <- Α[Ι]
     Ι <- Ι+1
  αλλιώς
     Γ[Κ] <- Β[J]
     J <- J +1
  Τέλος_αν
Τέλος_επανάληψης

Αποτελέσματα // Γ //
Τέλος Συγχώνευση

[Λαμπράκης Μανώλης]

Καλημέρα σε άλους, χρόνια πολλά και χρονιά

διάβασα σε πολλές παραλλαγές διάφορα θέματα  για συγχώνευση πχ δύο μονοδιάστατων πινάκων με μάγαθος Α και Β . Για να δω αν τα κατάλαβα καλά, γράφω τρεις προτάσεις συγκεντρωτικές να ρωτήσω την γνώμη σας

1) αν μία άσκηση ζητάει συγχώνευση δύο πινάκων, δίχως να είναι ταξινομημένοι, μποροούμε να τους συγχωνεύσουμε σε έναν με μέγεθος Α+Β δίχως να χρειάζεται να κάνουμε ταξινόμηση

2) αν οι δύο πίνακες είναι ταξινομημένοι και τους συγχωνεύσουμε σε έναν με μέγαθος Α+Β, πρέπει να ταξινομήσουμε απαραίτητα και τον τελικό, αλλιώς είναι λάθος

3) αν σκεφτούμε εν τέλει να ταξινομήσουμε τον τελικό πίνακα, μπορούμε να το κάνουμε είτε με την "έξυπνη συγχώνευση" ταξινομώντας απευθείας τα στοιχεία του τελικού , είτε σε "δύο βήματα", δηλαδή να ενώσουμε τους δύο πίνακες, και στην συνέχεια να ταξινομήσουμε τον τελικό ....

εγω θα έλεγα

1) --> σωστή, αν δεν είναι ταξινομημένοι οι αρχικοί, δεν χρειάζεται ταξινόμηση στον τελικό (είναι άραγε "λάθος" να ταξινομήσουμε τον τελικό  ?? )
2) --> σωστή, αν είναι ταξινομημένοι οι αρχικοί, πρέπει να έιναι και ο τελικός  (αν τους ενώσουμε δίχως ταξινόμηση του τελικού είναι λάθος ?? )
3) --> σωστή, μπορούμε να ταξινομήσουμε όπως θέλουμε (έχουμε υποχρέωση να είναι "απευθείας" ταξινομημένος και ο τελικό ??)

θα ήθελα τις γνώμες σας

ευχαριστώ

[petrosp13]

Η συγχώνευση και η ταξινόμηση είναι 2 διαφορετικές λειτουργίες επί των δομών δεδομένων
Νομίζω ότι όλη η σύγχυση προέρχεται από την ανόητη έκφραση του βιβλίου που μιλάει για συγχώνευση 2 ή περισσότερων ταξινομημένων πινάκων σε έναν επίσης ταξινομημένο
Λες και δεν είναι εφικτό αυτό σε αταξινόμητους πίνακες

[Λαμπράκης Μανώλης]

Οπότε συμφωνούμε και στις παραπάνω προτάσεις ?? το θέμα με όλες τις "γκρίζες ζώνες" του βιβλίου, είναι ότι εμείς πρέπει να δώσουμε μία απάντηση στους μαθητές...μπορεί το "δεν είναι ακριβώς έτσι" να είναι η πιο πλήρης ή η σωστή απάντηση σε κάποιες περιπτώσεις, όμως οι μαθητές περιμένουν μία απάντηση και εμείς πρέπει να δώσουμε μία, καλώς ή κακώς....

ευχαριστώ

[evry]

Όταν οι πίνακες δεν είναι ταξινομημένοι μιλάμε για συνένωση και όχι για συγχώνευση.
Τον όρο συγχώνευση τον χρησιμοποιούμε συνήθως για ταξινομημένους πίνακες, από εκεί προκύπτει και η ταξινόμηση merge-sort.
Παραθέτω και το σχετικό λήμμα στη wikipedia για το τι είναι συγχώνευση
http://en.wikipedia.org/wiki/Merge_algorithm

Για αυτό και στο βιβλίο όταν μιλάει για συγχώνευση στο κεφ.9 μιλάει αποκλειστικά για ταξινομημένους πίνακες. Η ιδέα είναι να σχεδιάσεις αλγόριθμο που να εκμεταλεύεται το γεγονός ότι είναι ταξινομημένοι και να έχει πολυπλοκότητα πολύ καλύτερη από O(n^2) που έχουν άλλοι αλγόριθμοι.

Προσωπικά πιστεύω ότι ο μόνος τρόπος να το ζητήσουν είναι να το περιγράψουν με λόγια, και να σου ζητήσουν να το δώσεις σε ψευδογλώσσα. Μόνο έτσι γιατί δεν μπορούν να σε υποχρεώσουν να δώσεις αλγόριθμο τάξης O(M+N).