Δυσκολία κατανόησης υλοποίησης Mergesort

[Επισκέπτης]

Γεια σας παιδιά. Προσπαθώ για μια εργασία να καταλάβω πως λειτουργεί η MergeSort αλλά δε μπορώ με αποτέλεσμα να μη μπορώ να συνεχίσω το project. Τι συμβαίνει στη πρώτη συνάρτηση mergesort; Δε μπορώ να καταλάβω πως βρίσκοντας απλώς σε κάθε βήμα το middle ταξινομεί τα στοιχεία των υποπινάκων. Επίσης, η πρώτη που καλείται (mergesort(low, middle)) εκτελείται συνεχώς αναδρομικά ώσπου θα παραβιαστεί η συνθήκη της if και άρα δε θα μπει στις άλλες δύο από κάτω. Έτσι μου φαίνεται εμένα. Μπορεί κανείς να μου εξηγήσει πως λειτουργεί; Ο πίνακας numbers είναι αυτός με τα στοιχεία προς ταξινόμηση.

private void mergesort(int low, int high) {
                // check if low is smaller than high, if not then the array is sorted
                if (low < high) {
                        // Get the index of the element which is in the middle
                        int middle = low + (high - low) / 2;
                        // Sort the left side of the array
                        mergesort(low, middle);
                        // Sort the right side of the array
                        mergesort(middle + 1, high);
                        // Combine them both
                        merge(low, middle, high);
                }
        }

        private void merge(int low, int middle, int high) {

                // Copy both parts into the helper array
                for (int i = low; i <= high; i++) {
                        helper[i] = numbers[i];
                }

                int i = low;
                int j = middle + 1;
                int k = low;
                // Copy the smallest values from either the left or the right side back
                // to the original array
                while (i <= middle && j <= high) {
                        if (helper[i] <= helper[j]) {
                                numbers[k] = helper[i];
                                i++;
                        } else {
                                numbers[k] = helper[j];
                                j++;
                        }
                        k++;
                }
                // Copy the rest of the left side of the array into the target array
                while (i <= middle) {
                        numbers[k] = helper[i];
                        k++;
                        i++;
                }

        }

[jimisvog]

Με βάση την θεωρία της mergesort και τον κώδικά σου:

 

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

 

 

Μια εικόνα που δείχνει τα βήματα σε ένα sample:

 

[Επισκέπτης]

Τότε γιατί στα comments πάνω από τις συναρτήσεις γράφει τη λέξη ''sort'' και με παιδεύει; Έλεος!

 

Ωραία, εξήγησε μου όμως λίγο: όταν καλείτε συνεχώς αναδρομικά η πρώτη που δέχεται ως ορίσματα low,middle και συνεχώς καλείται κάποια στιγμή θα παραβιαστεί η if και θα φτάσει στο τέλος η συνάρτηση. Όμως οι δύο συναρτήσεις από κάτω δε θα έχουν τρέξει γιατί βρίσκονται και αυτές μέσα στην if.

[gpolic]

Τότε γιατί στα comments πάνω από τις συναρτήσεις γράφει τη λέξη ''sort'' και με παιδεύει; Έλεος!

 

Ωραία, εξήγησε μου όμως λίγο: όταν καλείτε συνεχώς αναδρομικά η πρώτη που δέχεται ως ορίσματα low,middle και συνεχώς καλείται κάποια στιγμή θα παραβιαστεί η if και θα φτάσει στο τέλος η συνάρτηση. Όμως οι δύο συναρτήσεις από κάτω δε θα έχουν τρέξει γιατί βρίσκονται και αυτές μέσα στην if.

 

οταν θα παραβιαστει η if, οπως λες, τοτε θα "επιστρεψει" πισω η πρωτη mergesort.  Μετα θα εκτελεστει η 2η mergesort

οταν θα ολοκληρωσει και η 2η τοτε θα εκτελεστει και η merge

 

Διαβασε περισσοτερα για την "αναδρομη", ειναι ενα δυσκολο θεμα.

[Επισκέπτης]

Αααα δηλαδή επιστρέφει στο οποίο εκτελούνταν η συνάρτηση!!! Για αυτό δεν έβγαζα άκρη τόση ώρα. Ευχαριστώ πολύ.

[Lanike71]

Εντάξει, ανεπίτρεπτο φοιτητής πληροφορικής να μην έχει δει το σχετικό βίντεο :

 

https://www.youtube.com/watch?v=XaqR3G_NVoo

 

 

:-)