Τρόπος εφαρμογής της ταξινόμησης συγχώνευσης σε C ++ με παραδείγματα

Τι είναι το είδος συγχώνευσης; Η ταξινόμηση συγχώνευσης είναι ένας αλγόριθμος ταξινόμησης βασισμένος στη σύγκριση που ανήκει στην κατηγορία διαίρεσης και κατάκτησης. Το Merge sort χρησιμοποιείται για την ταξινόμηση ενός πίνακα που βασίζεται στη στρατηγική διαίρεσης και κατάκτησης που θα καλυφθεί εν συντομία σε αυτήν την ανάρτηση μαζί με άλλες έννοιες όπως ο αλγόριθμος με ένα παράδειγμα. Θα εξετάσουμε επίσης την πολυπλοκότητα του χρόνου συγχώνευσης στο C ++

Οι ακόλουθοι δείκτες θα καλυφθούν σε αυτό το άρθρο,

• Διαίρεση και κατάκτηση αλγορίθμου
• Κατανόηση του αλγορίθμου ταξινόμησης συγχώνευσης με ένα παράδειγμα
• Ψευδοκώδικας για συγχώνευση ταξινόμησης
• Πρόγραμμα σε C ++ για Merge Sort
• Η πολυπλοκότητα του χρόνου για το Merge Sort

Προχωρώντας με αυτό το άρθρο σχετικά με τη Συγχώνευση ταξινόμησης σε C ++

Διαίρεση και κατακτήστε τον αλγόριθμο

Εάν είστε ήδη εξοικειωμένοι με το πώς λειτουργεί η γρήγορη ταξινόμηση, ίσως γνωρίζετε τη στρατηγική διαίρεσης και κατάκτησης. Το Divide and Conquer περιλαμβάνει τρία σημαντικά βήματα. Για την κατανόηση αυτών των βημάτων ας εξετάσουμε έναν πίνακα Γεια σας [] έχοντας αρχικό ευρετήριο «a» και τελικό ευρετήριο «n», επομένως μπορούμε να γράψουμε τον πίνακα μας με τον ακόλουθο τρόπο Γεια σας

Διαίρεση - Η πρωταρχική κίνηση ή το πρώτο βήμα της διαίρεσης και της κατάκτησης είναι να διαιρέσουμε το δεδομένο πρόβλημα σε υπο-προβλήματα ή υπο-μέρη. Το συμπέρασμα εδώ είναι ότι τα δευτερεύοντα προβλήματα πρέπει να είναι παρόμοια με το αρχικό πρόβλημα και μικρότερο σε μέγεθος. Στην περίπτωσή μας θα χωρίσουμε τον πίνακα μας σε 2 μισά [a & hellip.m] [m + 1 & hellip..n] m βρίσκεται στη μέση ενός δείκτη a και n

Conquer- Μόλις τελειώσουμε διαιρώντας το πρόβλημά μας σε δευτερεύοντα προβλήματα. Λύουμε αυτά τα υποπροβλήματα αναδρομικά.

Combine- Σε αυτό το βήμα, συνδυάζουμε όλες τις λύσεις των υπο-προβλημάτων μας με τον κατάλληλο τρόπο. Με άλλα λόγια, συνδυάζουμε 2 διαφορετικούς πίνακες ταξινόμησης για να σχηματίσουμε έναν πίνακα ταξινόμησης. Εκεί έχουμε την ταξινομημένη σειρά μας.

Προχωρώντας με αυτό το άρθρο σχετικά με τη Συγχώνευση ταξινόμησης σε C ++

Κατανόηση του αλγορίθμου συγχώνευσης ταξινόμησης με ένα παράδειγμα

Σε αυτό το σημείο, γνωρίζουμε ποια προσέγγιση θα χρησιμοποιηθεί από το είδος της συγχώνευσης. Ας δούμε λοιπόν ένα παράδειγμα και ακολουθήστε κάθε βήμα από το Hello [] χωρίς ταξινόμηση σε ταξινομημένο πίνακα.
Παράδειγμα- Γεια σας [10, 3, 7, 1, 15, 14, 9, 22]

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

1. Πρώτον, θεωρήσαμε έναν πίνακα Γεια σας [10, 3, 7, 1, 15, 14, 9, 22] σε αυτόν τον πίνακα υπάρχουν συνολικά 8 στοιχεία

2. Όπως είδαμε νωρίτερα, το είδος συγχώνευσης χρησιμοποιεί την προσέγγιση διαίρεσης και κατάκτησης για να ταξινομήσει τα στοιχεία. Βρήκαμε m που βρίσκεται στη μέση του πίνακα μας και διαιρέσαμε τον πίνακα μας από τη μέση όπου m = (a - n) / 2 'a' είναι ο δείκτης του αριστερότερου στοιχείου και n είναι ο δείκτης του δεξιού στοιχείου του πίνακα μας .

τι είναι αδιέξοδο στην Ιάβα

3. Μετά την πρώτη κατηγορία, έχουμε 2 μέρη που αποτελούνται από 4 στοιχεία το καθένα. Ας δούμε το πρώτο ημίχρονο [10, 3, 7, 1].

4. Διαιρούμε τα [10, 3, 7, 1] σε 2 μέρη [10, 3] και [7, 1]. Μετά από αυτό τα χωρίζουμε περαιτέρω σε [10], [3], [7], [1]. Δεν είναι δυνατή η περαιτέρω διαίρεση, καθώς δεν μπορούμε να υπολογίσουμε το m. μια λίστα που περιέχει ένα μόνο στοιχείο θεωρείται πάντα ταξινομημένη.

5. Πώς πραγματοποιείται η συγχώνευση; Ας ανακαλύψουμε. Πρώτα [10] και [3] συγκρίνονται και συγχωνεύονται με αύξουσα σειρά [3, 10] με τον ίδιο τρόπο που παίρνουμε [1, 7]

6. Μετά από αυτό, συγκρίνουμε [3, 10] και [1, 7]. Μόλις συγκριθούν, τα συγχωνεύουμε με αύξουσα σειρά και παίρνουμε [1, 3, 7, 10].

7. [15, 14, 9, 2] χωρίζεται και συνδυάζεται με παρόμοιο τρόπο για να σχηματιστεί [9, 14, 15, 22].

8. Στο τελευταίο βήμα συγκρίνουμε και συνδυάζουμε [15, 14, 9, 2] [9, 14, 15, 22] για να μας δώσουμε την ταξινομημένη σειρά μαςδηλ. [1, 3, 7, 9, 10, 14, 15, 22].

Προχωρώντας με αυτό το άρθρο σχετικά με τη Συγχώνευση ταξινόμησης σε C ++

Ψευδοκώδικας για συγχώνευση ταξινόμησης

Ξεκινήστε αν μείνει
Η συνάρτηση mergeSort () καλείται αναδρομικά για να διαιρέσει τον πίνακα μας έως ότου γίνει ένα μόνο στοιχείο και η συνάρτηση συγχώνευσης () χρησιμοποιείται για τη συγχώνευση των ταξινομημένων πινάκων.
  Προχωρώντας με αυτό το άρθρο σχετικά με τη Συγχώνευση ταξινόμησης σε C ++
 Συγχώνευση προγράμματος ταξινόμησης σε C ++ 
#include #include #include χρησιμοποιώντας χώρο ονομάτων std void συγχώνευση (int a [], int Firstindex, int m, int Lastindex) // συγχωνεύει τις δευτερεύουσες συστοιχίες που δημιουργούνται ενώ το τμήμα void mergeSort (int a [], int Firstindex, int Lastindex) {if (Firstindex)μέγεθος int Γεια [μέγεθος], μου λέω<<'Enter the elements of the array one by one:n' for(i=0 i>Γεια σας [i] mergeSort (Hello, 0, size - 1) cout<<'The Sorted List isn' for(i=0 i
 Παραγωγή- 
Προχωρώντας με αυτό το άρθρο σχετικά με τη Συγχώνευση ταξινόμησης σε C ++
 Χρόνος πολυπλοκότητας 
Η πολυπλοκότητα του χρόνου είναι μια σημαντική πτυχή που πρέπει να ληφθεί υπόψη όταν μιλάμε για αλγόριθμους. Η ταξινόμηση συγχώνευσης θεωρείται ότι έχει μεγάλη χρονική πολυπλοκότητα σε σύγκριση με άλλους αλγόριθμους ταξινόμησης.
Χειρότερος χρόνος λειτουργίας- O (n log n) 
Καλύτερος χρόνος λειτουργίας - O (n log n) 
Μέσος χρόνος εκτέλεσης- O (n log n)
Με αυτό, καταλήγουμε σε αυτό το άρθρο Συγχώνευση σε άρθρο C ++. Εάν θέλετε να μάθετε περισσότερα, δείτε το   από την Edureka, μια αξιόπιστη διαδικτυακή εταιρεία μάθησης. Το μάθημα εκπαίδευσης και πιστοποίησης Java J2EE και SOA της Edureka έχει σχεδιαστεί για να σας εκπαιδεύσει τόσο για βασικές όσο και για προχωρημένες ιδέες Java μαζί με διάφορα πλαίσια Java όπως το Hibernate & Spring.
 Έχετε μια ερώτηση για εμάς; Παρακαλώ αναφέρετέ το στην ενότητα σχολίων αυτού του ιστολογίου και θα επικοινωνήσουμε μαζί σας το συντομότερο δυνατό.