Η ταξινόμηση συγχώνευσης είναι ένας από τους βασικούς αλγόριθμους της πληροφορικής, που διατυπώθηκε το 1945 από τον σπουδαίο μαθηματικό John von Neumann. Ενώ συμμετείχε στο Manhattan Project, ο Neumann αντιμετώπισε την ανάγκη να επεξεργαστεί αποτελεσματικά τεράστιες ποσότητες δεδομένων. Η μέθοδος που ανέπτυξε χρησιμοποιούσε την αρχή του «διαίρει και βασίλευε», η οποία μείωσε σημαντικά τον απαιτούμενο χρόνο για εργασία.
Αρχή και χρήση του αλγορίθμου
Η μέθοδος ταξινόμησης συγχώνευσης χρησιμοποιείται σε προβλήματα ταξινόμησης δομών που έχουν διατεταγμένη πρόσβαση σε στοιχεία, όπως πίνακες, λίστες, ροές.
Κατά την επεξεργασία, το αρχικό μπλοκ δεδομένων χωρίζεται σε μικρά στοιχεία, έως ένα στοιχείο, το οποίο στην πραγματικότητα είναι ήδη μια ταξινομημένη λίστα. Στη συνέχεια επανασυναρμολογείται με τη σωστή σειρά.
Η ταξινόμηση ενός πίνακα συγκεκριμένου μήκους απαιτεί μια πρόσθετη περιοχή μνήμης του ίδιου μεγέθους, στην οποία ο ταξινομημένος πίνακας συλλέγεται σε μέρη.
Η μέθοδος μπορεί να χρησιμοποιηθεί για την παραγγελία οποιουδήποτε συγκρίσιμου τύπου δεδομένων, όπως αριθμούς ή συμβολοσειρές.
Η συγχώνευση ταξινομήθηκεοικόπεδα
Για να κατανοήσουμε τον αλγόριθμο, ας ξεκινήσουμε την ανάλυσή του από το τέλος - από τον μηχανισμό συγχώνευσης ταξινομημένων μπλοκ.
Ας φανταστούμε ότι έχουμε δύο πίνακες αριθμών ταξινομημένων με οποιονδήποτε τρόπο που πρέπει να συνδυαστούν μεταξύ τους για να μην σπάσει η ταξινόμηση. Για απλότητα, θα ταξινομήσουμε τους αριθμούς με αύξουσα σειρά.
Στοιχειώδες παράδειγμα: και οι δύο πίνακες αποτελούνται από ένα στοιχείο ο καθένας.
int arr1={31}; int arr2={18};
Για να τα συγχωνεύσετε, πρέπει να πάρετε το μηδενικό στοιχείο του πρώτου πίνακα (μην ξεχνάτε ότι η αρίθμηση ξεκινά από το μηδέν) και το μηδενικό στοιχείο του δεύτερου πίνακα. Αυτά είναι, αντίστοιχα, το 31 και το 18. Σύμφωνα με τη συνθήκη ταξινόμησης, ο αριθμός 18 θα πρέπει να έρχεται πρώτος, αφού είναι μικρότερος. Απλώς βάλτε τους αριθμούς με τη σωστή σειρά:
int αποτέλεσμα={18, 31};
Ας δούμε ένα πιο περίπλοκο παράδειγμα, όπου κάθε πίνακας αποτελείται από πολλά στοιχεία:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Ο αλγόριθμος συγχώνευσης θα αποτελείται από τη διαδοχική σύγκριση μικρότερων στοιχείων και την τοποθέτησή τους στον πίνακα που προκύπτει με τη σωστή σειρά. Για να παρακολουθούμε τους τρέχοντες δείκτες, ας εισαγάγουμε δύο μεταβλητές - index1 και index2. Αρχικά, τα μηδενίζουμε, αφού οι πίνακες είναι ταξινομημένοι και τα μικρότερα στοιχεία βρίσκονται στην αρχή.
int index1=0; int index2=0;
Ας γράψουμε ολόκληρη τη διαδικασία συγχώνευσης βήμα προς βήμα:
- Πάρτε το στοιχείο με index1 από τον πίνακα arr1 και το στοιχείο με index2 από τον πίνακα arr2.
- Συγκρίνετε, επιλέξτε το μικρότερο από αυτά και βάλτε μέσαπίνακας που προκύπτει.
- Αύξηση του τρέχοντος δείκτη του μικρότερου στοιχείου κατά 1.
- Συνεχίστε από το πρώτο βήμα.
Στην πρώτη τροχιά, η κατάσταση θα μοιάζει με αυτό:
index1=0; δείκτης2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; ευρετήριο1++; αποτέλεσμα[0]=arr1[0]; // αποτέλεσμα=[2]
Στη δεύτερη στροφή:
index1=1; δείκτης2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; ευρετήριο2++; αποτέλεσμα[1]=arr2[0]; // αποτέλεσμα=[2, 5]
Τρίτο:
index1=1; δείκτης2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; ευρετήριο2++; αποτέλεσμα[2]=arr2[1]; // αποτέλεσμα=[2, 5, 6]
Και ούτω καθεξής, έως ότου το αποτέλεσμα είναι ένας πλήρως ταξινομημένος πίνακας: {2, 5, 6, 17, 21, 19, 30, 45}.
Μπορεί να προκύψουν ορισμένες δυσκολίες εάν συγχωνευθούν πίνακες με διαφορετικά μήκη. Τι γίνεται αν ένας από τους τρέχοντες δείκτες έχει φτάσει στο τελευταίο στοιχείο και υπάρχουν ακόμα μέλη στον δεύτερο πίνακα;
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 βήμα δείκτης1=0, δείκτης2=0; 1 2 αποτέλεσμα={1, 2}; // Δείκτης 3 βημάτων1=1, δείκτης2=1; 4 < 5 αποτέλεσμα={1, 2, 4}; //4 βήμα δείκτης1=2, δείκτης 2=1 ??
Η μεταβλητή index1 έχει φτάσει την τιμή 2, αλλά ο πίνακας arr1 δεν έχει στοιχείο με αυτόν τον δείκτη. Όλα είναι απλά εδώ: απλώς μεταφέρετε τα υπόλοιπα στοιχεία του δεύτερου πίνακα στον προκύπτοντα, διατηρώντας τη σειρά τους.
result={1, 2, 4, 5, 6, 7, 9};
Αυτή η κατάσταση μας δείχνει την ανάγκηαντιστοιχίστε τον τρέχοντα δείκτη ελέγχου με το μήκος του πίνακα που συγχωνεύεται.
Σχήμα συγχώνευσης για διατεταγμένες ακολουθίες (Α και Β) διαφορετικών μηκών:
- Αν το μήκος και των δύο ακολουθιών είναι μεγαλύτερο από 0, συγκρίνετε A[0] και B[0] και μετακινήστε τη μικρότερη στην προσωρινή μνήμη.
- Αν το μήκος μιας από τις ακολουθίες είναι 0, πάρτε τα υπόλοιπα στοιχεία της δεύτερης ακολουθίας και, χωρίς να αλλάξετε τη σειρά τους, μετακινηθείτε στο τέλος του buffer.
Εφαρμογή του δεύτερου σταδίου
Ένα παράδειγμα σύνδεσης δύο ταξινομημένων πινάκων στην Java δίνεται παρακάτω.
int a1=νέο int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=νέο int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=νέο int[a1.length + a2.length]; int i=0, j=0; for (int k=0; k a1.length-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.length-1) { int a=a1; a3[k]=a; i++; } else if (a1 < a2[j]) { int a=a1; a3[k]=a; i++; } else { int b=a2[j]; a3[k]=b; j++; } }
Εδώ:
- a1 και a2 είναι οι αρχικοί ταξινομημένοι πίνακες που πρέπει να συγχωνευθούν;
- a3 – τελικός πίνακας;
- Τα i και j είναι δείκτες των τρεχόντων στοιχείων για τους πίνακες a1 και a2.
Το πρώτο και το δεύτερο εάν οι συνθήκες διασφαλίζουν ότι οι δείκτες δεν υπερβαίνουν το μέγεθος του πίνακα. Το τρίτο και το τέταρτο μπλοκ συνθήκης, αντίστοιχα, μετακινούνται στον προκύπτοντα πίνακα του μικρότερου στοιχείου.
Διαίρει και βασίλευε
Λοιπόν, μάθαμε να συγχωνεύουμε τα ταξινομημένασυλλογές αξιών. Μπορούμε να πούμε ότι το δεύτερο μέρος του αλγορίθμου ταξινόμησης συγχώνευσης - η ίδια η συγχώνευση - έχει ήδη ταξινομηθεί.
Ωστόσο, πρέπει ακόμα να κατανοήσετε πώς να μεταβείτε από τον αρχικό μη ταξινομημένο πίνακα αριθμών σε πολλούς ταξινομημένους που μπορούν να συγχωνευθούν.
Ας εξετάσουμε το πρώτο στάδιο του αλγορίθμου και ας μάθουμε πώς να διαχωρίζουμε πίνακες.
Αυτό δεν είναι δύσκολο - ο αρχικός κατάλογος τιμών χωρίζεται στο μισό, στη συνέχεια κάθε τμήμα είναι επίσης διακλαδισμένο και ούτω καθεξής μέχρι να ληφθούν πολύ μικρά μπλοκ.
Το μήκος τέτοιων ελάχιστων στοιχείων μπορεί να είναι ίσο με ένα, δηλαδή, μπορούν να είναι τα ίδια ένας ταξινομημένος πίνακας, αλλά αυτό δεν είναι απαραίτητη προϋπόθεση. Το μέγεθος του μπλοκ καθορίζεται εκ των προτέρων και οποιοσδήποτε κατάλληλος αλγόριθμος ταξινόμησης που λειτουργεί αποτελεσματικά με πίνακες μικρών μεγεθών (για παράδειγμα, γρήγορη ταξινόμηση ή ταξινόμηση εισαγωγής) μπορεί να χρησιμοποιηθεί για την παραγγελία του.
Έτσι μοιάζει.
// αρχικός πίνακας {34, 95, 10, 2, 102, 70}; // πρώτος διαχωρισμός {34, 95, 10} και {2, 102, 70}. // δεύτερη διαίρεση {34} και {95, 10} και {2} και {102, 70}
Τα μπλοκ που προκύπτουν, που αποτελούνται από 1-2 στοιχεία, είναι πολύ εύκολο να τακτοποιήσουν.
Μετά από αυτό, πρέπει να συγχωνεύσετε τους ήδη ταξινομημένους μικρούς πίνακες σε ζεύγη, διατηρώντας τη σειρά των μελών, κάτι που έχουμε ήδη μάθει να κάνουμε.
Υλοποίηση του πρώτου σταδίου
Η αναδρομική κατάτμηση ενός πίνακα φαίνεται παρακάτω.
void mergeSort(T a, long start, long finish) { long split; αν(έναρξη < φινίρισμα) { split=(start + finish)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); συγχώνευση (a, start, split, finish); } }
Τι συμβαίνει σε αυτόν τον κωδικό:
-
Η συνάρτηση συγχώνευσης Ταξινόμηση λαμβάνει τον αρχικό πίνακα
a
και το αριστερό και το δεξιό περίγραμμα της περιοχής που πρόκειται να ταξινομηθεί (οι δείκτες ξεκινούν και
- finish).
-
Αν το μήκος αυτής της ενότητας είναι μεγαλύτερο από ένα (
start < finish
), τότε χωρίζεται σε δύο μέρη (με δείκτη
- split), και το καθένα ταξινομείται αναδρομικά.
-
Στην κλήση της αναδρομικής συνάρτησης για την αριστερή πλευρά, μεταβιβάζονται ο αρχικός δείκτης της γραφικής παράστασης και ο δείκτης
split
. Για το σωστό, αντίστοιχα, η αρχή θα είναι
- (split + 1) και το τέλος θα είναι το τελευταίο ευρετήριο της αρχικής ενότητας.
-
Η συνάρτηση
merge
λαμβάνει δύο διατεταγμένες ακολουθίες (
a[start]…a[split]
και
- a[split +1]…a[finish]) και τα συγχωνεύει με σειρά ταξινόμησης.
Οι μηχανισμοί της συνάρτησης συγχώνευσης συζητήθηκαν παραπάνω.
Γενικό σχήμα του αλγορίθμου
Η μέθοδος του πίνακα ταξινόμησης συγχώνευσης αποτελείται από δύο μεγάλα βήματα:
- Χωρίστε τον μη ταξινομημένο αρχικό πίνακα σε μικρά κομμάτια.
- Συλλέξτε τα σε ζευγάρια, ακολουθώντας τον κανόνα ταξινόμησης.
Μια μεγάλη και σύνθετη εργασία αναλύεται σε πολλές απλές, οι οποίες λύνονται διαδοχικά, οδηγώντας στο επιθυμητό αποτέλεσμα.
Αξιολόγηση μεθόδου
Η χρονική πολυπλοκότητα της ταξινόμησης συγχώνευσης καθορίζεται από το ύψος του δέντρου διαχωρισμούαλγόριθμος και ισούται με τον αριθμό των στοιχείων του πίνακα (n) επί τον λογάριθμό του (log n). Μια τέτοια εκτίμηση ονομάζεται λογαριθμική.
Αυτό είναι και ένα πλεονέκτημα και ένα μειονέκτημα της μεθόδου. Ο χρόνος λειτουργίας του δεν αλλάζει ακόμη και στη χειρότερη περίπτωση, όταν ο αρχικός πίνακας ταξινομείται με αντίστροφη σειρά. Ωστόσο, κατά την επεξεργασία πλήρως ταξινομημένων δεδομένων, ο αλγόριθμος δεν παρέχει κέρδος χρόνου.
Είναι επίσης σημαντικό να σημειώσετε το κόστος μνήμης της μεθόδου ταξινόμησης συγχώνευσης. Είναι ίσα με το μέγεθος της αρχικής συλλογής. Σε αυτήν την επιπρόσθετα εκχωρημένη περιοχή, ένας ταξινομημένος πίνακας συναρμολογείται από τα κομμάτια.
Εφαρμογή του αλγορίθμου
Η ταξινόμηση συγχώνευσης Pascal εμφανίζεται παρακάτω.
Διαδικασία MergeSort(όνομα: συμβολοσειρά; var f: κείμενο); Var a1, a2, s, i, j, kol, tmp: ακέραιος; f1, f2: κείμενο; β: boolean Begincol:=0; Assign(f, name); επαναφορά (f); Ενώ δεν το EOF(f) ξεκινάει την ανάγνωση(f, a1). Inc(col); τέλος; κλείσιμο(f); Assign(f1, '{όνομα του 1ου βοηθητικού αρχείου}'); Assign(f2, '{όνομα 2ου βοηθητικού αρχείου}'); s:=1; Ενώ το (s<kol) ξεκινάει το Reset(f); rewrite(f1); rewrite(f2); Για το i:=1 έως το kol div 2 ξεκινάμε Read(f, a1); Write(f1, a1, ' '); τέλος; Εάν (kol div 2) mod s0, τότε ξεκινήστε tmp:=kol div 2; Ενώ το tmp mod s0 ξεκινάει Read(f, a1); Write(f1, a1, ' '); Inc(tmp); τέλος; τέλος; Ενώ δεν EOF(f) ξεκινά Read(f, a2). Write(f2, a2, ' '); τέλος; κλείσιμο(f); κλείσιμο(f1); κλείσιμο(f2); ξαναγράψω(f); επαναφορά (f1); επαναφορά (f2); Read(f1, a1); Read(f2, a2); Ενώ (όχι EOF(f1)) και (όχι EOF(f2)) αρχίζουν i:=0; j:=0; β:=αληθής; Ενώ τα (b) και (όχι EOF(f1)) και (όχι EOF(f2)) ξεκινούν Εάν (a1<a2) τότε ξεκινήστεWrite(f, a1, ' '); Read(f1, a1); Inc(i); Τέλος αλλού αρχίζει Write(f, a2, ' '); Read(f2, a2); inc(j); τέλος; Αν (i=s) ή (j=s) τότε b:=false; τέλος; Αν όχι b τότε ξεκινήστε ενώ (i<s) και (όχι EOF(f1)) ξεκινήστε Write(f, a1, ' '); Read(f1, a1); Inc(i); τέλος; Ενώ τα (j<s) και (όχι EOF(f2)) ξεκινούν Write(f, a2, ' '); Read(f2, a2); inc(j); τέλος; τέλος; τέλος; Ενώ δεν είναι EOF(f1) ξεκινάει tmp:=a1; Read(f1, a1); Αν όχι EOF(f1) τότε Write(f, tmp, ' ') else Write(f, tmp); τέλος; Ενώ δεν είναι EOF(f2) ξεκινάει tmp:=a2; Read(f2, a2); Αν όχι EOF(f2) τότε Write(f, tmp, ' ') else Write(f, tmp); τέλος; κλείσιμο(f); κλείσιμο(f1); κλείσιμο(f2); s:=s2; τέλος; Διαγραφή(f1); Διαγραφή(f2); Τέλος;
Οπτικά, η λειτουργία του αλγορίθμου μοιάζει με αυτό (πάνω - μη διατεταγμένη ακολουθία, κάτω - διατεταγμένη).
Ταξινόμηση εξωτερικών δεδομένων
Πολύ συχνά υπάρχει ανάγκη ταξινόμησης ορισμένων δεδομένων που βρίσκονται στην εξωτερική μνήμη του υπολογιστή. Σε ορισμένες περιπτώσεις, είναι εντυπωσιακού μεγέθους και δεν μπορούν να τοποθετηθούν στη μνήμη RAM για να διευκολυνθεί η πρόσβαση σε αυτά. Για τέτοιες περιπτώσεις, χρησιμοποιούνται μέθοδοι εξωτερικής ταξινόμησης.
Η ανάγκη πρόσβασης σε εξωτερικά μέσα υποβαθμίζει την απόδοση του χρόνου επεξεργασίας.
Η πολυπλοκότητα της εργασίας είναι ότι ο αλγόριθμος μπορεί να έχει πρόσβαση μόνο σε ένα στοιχείο της ροής δεδομένων κάθε φορά. Και σε αυτήν την περίπτωση, ένα από τα καλύτερα αποτελέσματα εμφανίζεται με τη μέθοδο ταξινόμησης συγχώνευσης, η οποία μπορεί να συγκρίνει τα στοιχεία δύο αρχείων διαδοχικά το ένα μετά το άλλο.
Ανάγνωση δεδομένων απόεξωτερική πηγή, η επεξεργασία και η εγγραφή τους στο τελικό αρχείο πραγματοποιείται σε διατεταγμένα μπλοκ (σειρές). Σύμφωνα με τον τρόπο εργασίας με το μέγεθος των σειρών που ταξινομούνται, υπάρχουν δύο τύποι ταξινόμησης: απλή και φυσική συγχώνευση.
Απλή συγχώνευση
Με μια απλή συγχώνευση, το μήκος της σειράς είναι σταθερό.
Έτσι, στο αρχικό μη ταξινομημένο αρχείο, όλες οι σειρές αποτελούνται από ένα στοιχείο. Μετά το πρώτο βήμα, το μέγεθος αυξάνεται σε δύο. Επόμενο - 4, 8, 16 και ούτω καθεξής.
Λειτουργεί ως εξής:
- Το αρχείο προέλευσης (f) χωρίζεται σε δύο βοηθητικά - f1, f2.
- Συγχωνεύονται ξανά σε ένα αρχείο (f), αλλά ταυτόχρονα όλα τα στοιχεία συγκρίνονται σε ζεύγη και σχηματίζουν ζεύγη. Το μέγεθος της σειράς σε αυτό το βήμα γίνεται δύο.
- Το βήμα 1 επαναλαμβάνεται.
- Το βήμα 2 επαναλαμβάνεται, αλλά τα ήδη ταξινομημένα 2 συγχωνεύονται για να σχηματίσουν ταξινομημένα 4.
- Ο βρόχος συνεχίζεται, αυξάνοντας τη σειρά σε κάθε επανάληψη, μέχρι να ταξινομηθεί ολόκληρο το αρχείο.
Πώς γνωρίζετε ότι η εξωτερική ταξινόμηση με μια απλή συγχώνευση έχει ολοκληρωθεί;
- μήκος νέας σειράς (μετά τη συγχώνευση) όχι μικρότερο από τον συνολικό αριθμό στοιχείων;
- απομένει μόνο ένα επεισόδιο;
- Το βοηθητικό αρχείο f2 έμεινε κενό.
Τα μειονεκτήματα μιας απλής συγχώνευσης είναι: δεδομένου ότι το μήκος εκτέλεσης είναι σταθερό σε κάθε πέρασμα συγχώνευσης, τα μερικώς ταξινομημένα δεδομένα θα χρειαστούν τόσο χρόνο για να επεξεργαστούν όσο και εντελώς τυχαία δεδομένα.
Φυσική σύντηξη
Αυτή η μέθοδος δεν περιορίζει το μήκοςσειρά, αλλά επιλέγει το μέγιστο δυνατό.
Αλγόριθμος ταξινόμησης:
- Ανάγνωση της αρχικής ακολουθίας από το αρχείο f. Το πρώτο ληφθέν στοιχείο γράφεται στο αρχείο f1.
- Αν η επόμενη καταχώρηση ικανοποιεί τη συνθήκη ταξινόμησης, γράφεται εκεί, αν όχι, τότε στο δεύτερο βοηθητικό αρχείο f2.
- Με αυτόν τον τρόπο, όλες οι εγγραφές του αρχείου προέλευσης κατανέμονται και σχηματίζεται μια διατεταγμένη ακολουθία στο f1, η οποία καθορίζει το τρέχον μέγεθος της σειράς.
- Τα αρχεία f1 και f2 συγχωνεύονται.
- Ο κύκλος επαναλαμβάνεται.
Λόγω του μη σταθερού μεγέθους της σειράς, είναι απαραίτητο να επισημάνετε το τέλος της ακολουθίας με έναν ειδικό χαρακτήρα. Επομένως, κατά τη συγχώνευση, ο αριθμός των συγκρίσεων αυξάνεται. Επιπλέον, το μέγεθος ενός από τα βοηθητικά αρχεία μπορεί να είναι κοντά στο μέγεθος του αρχικού.
Κατά μέσο όρο, η φυσική συγχώνευση είναι πιο αποτελεσματική από την απλή συγχώνευση με εξωτερική ταξινόμηση.
Χαρακτηριστικά του αλγορίθμου
Όταν συγκρίνετε δύο ίδιες τιμές, η μέθοδος διατηρεί την αρχική τους σειρά, δηλαδή είναι σταθερή.
Η διαδικασία ταξινόμησης μπορεί να χωριστεί με μεγάλη επιτυχία σε πολλά νήματα.
Το βίντεο δείχνει ξεκάθαρα τη λειτουργία του αλγόριθμου ταξινόμησης συγχώνευσης.
