Πίνακας περιεχομένων
- Εισαγωγή
- Τι είναι το Merge Sort στην C++
- Προσέγγιση Διαίρει και Βασίλευε
- Αλγόριθμος ταξινόμησης συγχώνευσης
- Υλοποίηση συγχώνευσης ταξινόμησης σε C++
- συμπέρασμα
1. Εισαγωγή
Οι αλγόριθμοι ταξινόμησης στην επιστήμη των υπολογιστών χρησιμοποιούνται για τη διάταξη των δεδομένων σε αύξουσα ή φθίνουσα σειρά. Υπάρχουν πολλοί διαθέσιμοι αλγόριθμοι ταξινόμησης με διακριτές ιδιότητες. Η ταξινόμηση συγχώνευσης είναι μία από τις μεθόδους στη C++ που μπορεί να ταξινομήσει τους πίνακες.
2. Τι είναι το Merge Sort στη C++
Η ταξινόμηση συγχώνευσης χρησιμοποιεί την τεχνική διαίρει και βασίλευε που μπορεί να τακτοποιήσει τα στοιχεία ενός πίνακα. Μπορεί επίσης να ταξινομήσει τη λίστα των στοιχείων στη C++. Χωρίζει την είσοδο σε δύο μισά, ταξινομεί κάθε μισό ανεξάρτητα και στη συνέχεια τα συγχωνεύει με τη σωστή σειρά.
3. Προσέγγιση Διαίρει και Βασίλευε
Ο αλγόριθμος ταξινόμησης εφαρμόζει μια στρατηγική διαίρει και βασίλευε, η οποία συνεπάγεται τη διαίρεση του πίνακα εισόδου σε μικρότερες υποσυστοιχίες, την επίλυσή τους ξεχωριστά και, στη συνέχεια, τη συγχώνευση των αποτελεσμάτων για να παραχθεί μια ταξινομημένη έξοδος. Στην περίπτωση της ταξινόμησης συγχώνευσης, ο πίνακας χωρίζεται αναδρομικά σε δύο μισά μέχρι να μείνει μόνο ένα στοιχείο σε κάθε μισό.
4. Αλγόριθμος ταξινόμησης συγχώνευσης
Ο αλγόριθμος ταξινόμησης συγχώνευσης αποτελείται από δύο κύρια βήματα: διαίρεση και συγχώνευση. Τα βήματα είναι τα εξής:
4.1 Διαιρέστε
Ο αλγόριθμος ταξινόμησης συγχώνευσης ακολουθεί μια στρατηγική διαίρει και βασίλευε για την ταξινόμηση στοιχείων σε έναν πίνακα.
- Το πρώτο βήμα στον αλγόριθμο θα ελέγξει τα στοιχεία του πίνακα. Εάν περιέχει ένα στοιχείο, τότε θεωρείται ήδη ταξινομημένο και ο αλγόριθμος θα επιστρέψει τον ίδιο πίνακα χωρίς καμία αλλαγή.
- Εάν ο πίνακας περιέχει περισσότερα από ένα στοιχεία, ο αλγόριθμος προχωρά στη διαίρεση του σε δύο μισά: το αριστερό μισό και το δεξί μισό.
- Στη συνέχεια, ο αλγόριθμος ταξινόμησης συγχώνευσης εφαρμόζεται αναδρομικά στο αριστερό και το δεξί μισό του πίνακα, χωρίζοντάς τους αποτελεσματικά σε μικρότερους υποπίνακες και ταξινομώντας τους μεμονωμένα.
- Αυτή η αναδρομική διαδικασία συνεχίζεται έως ότου οι υποπίνακες περιέχουν μόνο ένα στοιχείο η καθεμία (σύμφωνα με το βήμα 1), οπότε μπορούν να συγχωνευθούν για να παραχθεί ένας τελικός, ταξινομημένος πίνακας εξόδου.
4.2 Συγχώνευση
Τώρα θα δούμε τα βήματα για τη συγχώνευση των πινάκων:
- Το πρώτο βήμα για τον αλγόριθμο ταξινόμησης συγχώνευσης περιλαμβάνει τη δημιουργία ενός κενού πίνακα.
- Στη συνέχεια, ο αλγόριθμος προχωρά στη σύγκριση των πρώτων στοιχείων του αριστερού και του δεξιού μισού του πίνακα εισόδου.
- Τα μικρότερα από τα δύο στοιχεία προστίθενται στον νέο πίνακα και στη συνέχεια αφαιρούνται από το αντίστοιχο μισό του πίνακα εισόδου.
- Στη συνέχεια επαναλαμβάνονται τα βήματα 2-3 μέχρι να αδειάσει ένα από τα μισά.
- Στη συνέχεια, όλα τα υπόλοιπα στοιχεία στο μη κενό μισό προστίθενται στον νέο πίνακα.
- Ο πίνακας που προκύπτει είναι πλέον πλήρως ταξινομημένος και αντιπροσωπεύει την τελική έξοδο του αλγορίθμου ταξινόμησης συγχώνευσης.
5. Υλοποίηση συγχώνευσης ταξινόμησης σε C++
Για την υλοποίηση της ταξινόμησης συγχώνευσης στη C++ ακολουθούνται δύο διαφορετικές μέθοδοι. Η χρονική πολυπλοκότητα και των δύο μεθόδων είναι ισοδύναμη, αλλά η χρήση των προσωρινών υποσυστοιχιών διαφέρει.
Η πρώτη μέθοδος για την ταξινόμηση συγχώνευσης στη C++ χρησιμοποιεί δύο προσωρινούς υποπίνακες, ενώ η δεύτερη χρησιμοποιεί μόνο έναν. Αξίζει να σημειωθεί ότι το συνολικό μέγεθος των δύο προσωρινών υποσυστοιχιών στην πρώτη μέθοδο είναι ίσο με το μέγεθος του αρχικού πίνακα στη δεύτερη μέθοδο, επομένως η πολυπλοκότητα του χώρου παραμένει σταθερή.
Μέθοδος 1 – Χρήση δύο υποσειρές θερμοκρασίας
Ακολουθεί ένα παράδειγμα προγράμματος για ταξινόμηση συγχώνευσης σε C++ χρησιμοποιώντας τη Μέθοδο 1, η οποία χρησιμοποιεί δύο προσωρινούς υποπίνακες:
#includeχρησιμοποιώντας το namespace std ;
κενός συγχώνευση ( ενθ αρ [ ] , ενθ μεγάλο , ενθ Μ , ενθ r )
{
ενθ n1 = Μ - μεγάλο + 1 ;
ενθ n2 = r - Μ ;
ενθ μεγάλο [ n1 ] , R [ n2 ] ;
Για ( ενθ Εγώ = 0 ; Εγώ < n1 ; Εγώ ++ )
μεγάλο [ Εγώ ] = αρ [ μεγάλο + Εγώ ] ;
Για ( ενθ ι = 0 ; ι < n2 ; ι ++ )
R [ ι ] = αρ [ Μ + 1 + ι ] ;
ενθ Εγώ = 0 , ι = 0 , κ = μεγάλο ;
ενώ ( Εγώ < n1 && ι < n2 ) {
αν ( μεγάλο [ Εγώ ] <= R [ ι ] ) {
αρ [ κ ] = μεγάλο [ Εγώ ] ;
Εγώ ++;
}
αλλού {
αρ [ κ ] = R [ ι ] ;
ι ++;
}
κ ++;
}
ενώ ( Εγώ < n1 ) {
αρ [ κ ] = μεγάλο [ Εγώ ] ;
Εγώ ++;
κ ++;
}
ενώ ( ι < n2 ) {
αρ [ κ ] = R [ ι ] ;
ι ++;
κ ++;
}
}
κενός συγχώνευση Ταξινόμηση ( ενθ αρ [ ] , ενθ μεγάλο , ενθ r )
{
αν ( μεγάλο < r ) {
ενθ Μ = μεγάλο + ( r - μεγάλο ) / 2 ;
συγχώνευση Ταξινόμηση ( αρ , μεγάλο , Μ ) ;
συγχώνευση Ταξινόμηση ( αρ , Μ + 1 , r ) ;
συγχώνευση ( αρ , μεγάλο , Μ , r ) ;
}
}
ενθ κύριος ( )
{
ενθ αρ [ ] = { 12 , έντεκα , 13 , 5 , 6 , 7 } ;
ενθ arr_size = μέγεθος του ( αρ ) / μέγεθος του ( αρ [ 0 ] ) ;
cout << 'Ο δεδομένος πίνακας είναι \n ' ;
Για ( ενθ Εγώ = 0 ; Εγώ < arr_size ; Εγώ ++ )
cout << αρ [ Εγώ ] << '' ;
συγχώνευση Ταξινόμηση ( αρ , 0 , arr_size - 1 ) ;
cout << ' \n Ταξινομημένος πίνακας είναι \n ' ;
Για ( ενθ Εγώ = 0 ; Εγώ < arr_size ; Εγώ ++ )
cout << αρ [ Εγώ ] << '' ;
ΕΠΙΣΤΡΟΦΗ 0 ;
}
Σε αυτό το πρόγραμμα, η συνάρτηση συγχώνευσης παίρνει τρία ορίσματα arr, l και r, τα οποία αντιπροσωπεύουν τον πίνακα που πρόκειται να ταξινομηθεί και δείχνει τους δείκτες του υποπίνακα που πρέπει να συγχωνευθεί. Η συνάρτηση βρίσκει πρώτα τα μεγέθη των δύο υπο-συστοιχιών που πρόκειται να συγχωνευθούν και, στη συνέχεια, δημιουργεί δύο προσωρινούς υποσυστοιχίες L και R για να αποθηκεύσει τα στοιχεία αυτών των υποσυστοιχιών. Στη συνέχεια συγκρίνει τα στοιχεία στα L και R και τα συγχωνεύει στον αρχικό πίνακα που ονομάζεται αρ με αύξουσα σειρά.
Η τεχνική divide-and-conquer χρησιμοποιείται από τη συνάρτηση mergeSort για να χωρίσει τον πίνακα σε δύο μισά αναδρομικά μέχρι να μείνει μόνο ένα στοιχείο έξω στον υποπίνακα. Στη συνέχεια συγχωνεύει τις δύο υποσυστοιχίες σε έναν ταξινομημένο υποπίνακα. Η συνάρτηση συνεχίζει να συγχωνεύει τους υποπίνακες εκτός και αν ταξινομήσει τον πλήρη πίνακα.
Στην κύρια συνάρτηση, ορίζουμε έναν πίνακα με 6 στοιχεία και καλούμε τη συνάρτηση mergeSort για να τον ταξινομήσουμε. Στο τέλος του κώδικα, εκτυπώνεται ο ταξινομημένος πίνακας.
Μέθοδος 2 – Χρήση One Temp Subray
Ακολουθεί ένα παράδειγμα προγράμματος για ταξινόμηση συγχώνευσης σε C++ χρησιμοποιώντας τη Μέθοδο 2, η οποία χρησιμοποιεί έναν μόνο προσωρινό υποπίνακα:
#includeχρησιμοποιώντας το namespace std ;
κενός συγχώνευση ( ενθ αρ [ ] , ενθ μεγάλο , ενθ Μ , ενθ r )
{
ενθ Εγώ , ι , κ ;
ενθ n1 = Μ - μεγάλο + 1 ;
ενθ n2 = r - Μ ;
// Δημιουργία προσωρινών υποσυστοιχιών
ενθ μεγάλο [ n1 ] , R [ n2 ] ;
// Αντιγραφή δεδομένων σε υποπίνακες
Για ( Εγώ = 0 ; Εγώ < n1 ; Εγώ ++ )
μεγάλο [ Εγώ ] = αρ [ μεγάλο + Εγώ ] ;
Για ( ι = 0 ; ι < n2 ; ι ++ )
R [ ι ] = αρ [ Μ + 1 + ι ] ;
// Συγχώνευση των προσωρινών δευτερευουσών συστοιχιών στον αρχικό πίνακα
Εγώ = 0 ;
ι = 0 ;
κ = μεγάλο ;
ενώ ( Εγώ < n1 && ι < n2 ) {
αν ( μεγάλο [ Εγώ ] <= R [ ι ] ) {
αρ [ κ ] = μεγάλο [ Εγώ ] ;
Εγώ ++;
}
αλλού {
αρ [ κ ] = R [ ι ] ;
ι ++;
}
κ ++;
}
// Αντιγράψτε τα υπόλοιπα στοιχεία του L[]
ενώ ( Εγώ < n1 ) {
αρ [ κ ] = μεγάλο [ Εγώ ] ;
Εγώ ++;
κ ++;
}
// Αντιγράψτε τα υπόλοιπα στοιχεία του R[]
ενώ ( ι < n2 ) {
αρ [ κ ] = R [ ι ] ;
ι ++;
κ ++;
}
}
κενός συγχώνευση Ταξινόμηση ( ενθ αρ [ ] , ενθ μεγάλο , ενθ r )
{
αν ( μεγάλο < r ) {
ενθ Μ = μεγάλο + ( r - μεγάλο ) / 2 ;
// Ταξινόμηση του αριστερού και του δεξιού μισού αναδρομικά
συγχώνευση Ταξινόμηση ( αρ , μεγάλο , Μ ) ;
συγχώνευση Ταξινόμηση ( αρ , Μ + 1 , r ) ;
// Συγχωνεύστε τα δύο ταξινομημένα μισά
συγχώνευση ( αρ , μεγάλο , Μ , r ) ;
}
}
ενθ κύριος ( )
{
ενθ αρ [ ] = { 12 , έντεκα , 13 , 5 , 6 , 7 } ;
ενθ arr_size = μέγεθος του ( αρ ) / μέγεθος του ( αρ [ 0 ] ) ;
cout << 'Ο δεδομένος πίνακας είναι \n ' ;
Για ( ενθ Εγώ = 0 ; Εγώ < arr_size ; Εγώ ++ )
cout << αρ [ Εγώ ] << '' ;
συγχώνευση Ταξινόμηση ( αρ , 0 , arr_size - 1 ) ;
cout << ' \n Ταξινομημένος πίνακας είναι \n ' ;
Για ( ενθ Εγώ = 0 ; Εγώ < arr_size ; Εγώ ++ )
cout << αρ [ Εγώ ] << '' ;
ΕΠΙΣΤΡΟΦΗ 0 ;
}
Αυτό το πρόγραμμα είναι όπως το προηγούμενο, αλλά αντί να χρησιμοποιεί δύο προσωρινές υποσυστοιχίες L και R, χρησιμοποιεί μία μόνο προσωρινή θερμοκρασία υποσυστοιχίας. Η συνάρτηση συγχώνευσης λειτουργεί με τον ίδιο τρόπο όπως πριν, αλλά αντί να αντιγράψει τα δεδομένα στα L και R, τα αντιγράφει στη θερμοκρασία. Στη συνέχεια συγχωνεύει τα στοιχεία προσωρινού πίνακα πίσω στο αρ που είναι ο αρχικός πίνακας.
Η συνάρτηση mergeSort είναι η ίδια με την προηγούμενη, με τη διαφορά ότι χρησιμοποιεί temp αντί για L και R για την αποθήκευση του προσωρινού υποπίνακα.
Στην κύρια συνάρτηση, ορίζουμε έναν πίνακα με 6 στοιχεία και καλούμε τη συνάρτηση mergeSort για να τον ταξινομήσουμε. Η εκτέλεση του κώδικα τελειώνει με την εκτύπωση του ταξινομημένου πίνακα στην οθόνη.
συμπέρασμα
Η ταξινόμηση συγχώνευσης είναι ένας αλγόριθμος που ταξινομεί στοιχεία πίνακα και χρησιμοποιεί την τεχνική διαίρει και βασίλευε και κάνει συγκρίσεις μεταξύ των στοιχείων. Η ταξινόμηση συγχώνευσης στη C++ έχει χρονική πολυπλοκότητα O(n log n) και είναι ιδιαίτερα αποτελεσματική για την ταξινόμηση μεγάλων πινάκων. Αν και απαιτεί πρόσθετη μνήμη για την αποθήκευση των συγχωνευμένων υποσυστοιχιών, η σταθερότητά του το καθιστά δημοφιλή επιλογή για ταξινόμηση.