Μενού

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

  • Κύριος
  • Αλλα
  • Συγχώνευση ταξινόμησης σε C ++ με παραδείγματα

merge sort c with examples

Δοκιμάστε Το Όργανο Μας Για Την Εξάλειψη Των Προβλημάτων

Τεχνική συγχώνευσης ταξινόμησης C ++.

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

Αυτά τα υποπροβλήματα στη συνέχεια συνδυάζονται ή συγχωνεύονται για να σχηματίσουν μια ενοποιημένη λύση.

=> Διαβάστε τη δημοφιλή σειρά εκπαιδευτικών C ++ εδώ.

Συγχώνευση ταξινόμησης

Τι θα μάθετε:

ποιο πρόγραμμα ανοίγει το αρχείο eps

ΣΦΑΙΡΙΚΗ ΕΙΚΟΝΑ

Η ταξινόμηση συγχώνευσης εκτελείται χρησιμοποιώντας τα ακόλουθα βήματα:

# 1) Η λίστα που θα ταξινομηθεί χωρίζεται σε δύο πίνακες ίσου μήκους διαιρώντας τη λίστα στο μεσαίο στοιχείο. Εάν ο αριθμός των στοιχείων στη λίστα είναι 0 ή 1, τότε η λίστα θεωρείται ταξινομημένη.

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

# 3) Οι ταξινομημένες δευτερεύουσες λίστες στη συνέχεια συνδυάζονται ή συγχωνεύονται μαζί για να σχηματίσουν μια πλήρη ταξινομημένη λίστα.

Γενικός αλγόριθμος

Ο γενικός ψευδοκώδικας για την τεχνική συγχώνευσης δίνεται παρακάτω.

Δηλώστε μια σειρά Arr του μήκους N
Εάν N = 1, το Arr έχει ήδη ταξινομηθεί
Εάν Ν> 1,
Αριστερά = 0, δεξιά = N-1
Εύρεση μέσου = (αριστερά + δεξιά) / 2
Κλήση merge_sort (Arr, αριστερά, μεσαία) => ταξινομήστε το πρώτο ημίχρονο αναδρομικά
Κλήση merge_sort (Arr, middle + 1, right) => ταξινομήστε το δεύτερο μισό αναδρομικά
Κλήση συγχώνευσης (Arr, αριστερά, μεσαία, δεξιά) για συγχώνευση ταξινομημένων συστοιχιών στα παραπάνω βήματα.
Εξοδος

Όπως φαίνεται στον παραπάνω ψευδο κώδικα, στον αλγόριθμο ταξινόμησης συγχώνευσης χωρίζουμε τον πίνακα σε μισό και ταξινομούμε κάθε μισό χρησιμοποιώντας αναλογικά τη συγχώνευση. Μόλις ταξινομηθούν οι δευτερεύουσες συστοιχίες ξεχωριστά, οι δύο δευτερεύουσες συστοιχίες συγχωνεύονται μαζί για να σχηματίσουν έναν πλήρη ταξινομημένο πίνακα.

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

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

procedure mergesort( array,N ) array – list of elements to be sorted N – number of elements in the list begin if ( N == 1 ) return array var array1 as array = a(0) ... a(N/2) var array2 as array = a(N/2+1) ... a(N) array1 = mergesort(array1) array2 = mergesort(array2) return merge( array1, array2 ) end procedure procedure merge(array1, array2 ) array1 – first array array2 – second array begin var c as array while ( a and b have elements ) if ( array1(0) > array2(0) ) add array2 (0) to the end of c remove array2 (0) from array2 else add array1 (0) to the end of c remove array1 (0) from array1 end if end while while ( a has elements ) add a(0) to the end of c remove a(0) from a end while while ( b has elements ) add b(0) to the end of c remove b(0) from b end while return c end procedure

Ας παρουσιάσουμε τώρα μια τεχνική συγχώνευσης με ένα παράδειγμα.

Απεικόνιση

συγχώνευση ταξινόμησης

Η παραπάνω εικόνα μπορεί να εμφανιστεί σε μορφή πίνακα παρακάτω:

ΠέρασμαΜη ταξινομημένη λίσταδιαιρέστεΤαξινομημένη λίστα
1{12, 23,2,43,51,35,19,4}{12,23,2,43}
{51,35,19,4}		{}
δύο{12,23,2,43}
{51,35,19,4}		{12.23} {2.43}
{51.35} {19.4}		{}
3{12.23} {2.43}
{51.35} {19.4}		{12.23} {2.43}
{35.51} {4.19}		{12.23} {2.43}
{35.51} {4.19}
4{12.23} {2.43}
{35.51} {4.19}		{2,12,23,43}
{4,19,35,51}		{2,12,23,43}
{4,19,35,51}
5{2,12,23,43}
{4,19,35,51}		{2,4,12,19,23,35,43,51}{2,4,12,19,23,35,43,51}
6{}{}{2,4,12,19,23,35,43,51}

Όπως φαίνεται στην παραπάνω αναπαράσταση, πρώτα ο πίνακας χωρίζεται σε δύο υπο-σειρές μήκους 4. Κάθε υπο-πίνακας διαιρείται περαιτέρω σε δύο επιπλέον υπο-σειρές μήκους 2. Κάθε υπο-πίνακας στη συνέχεια διαιρείται περαιτέρω σε υπο-συστοιχία από ένα στοιχείο το καθένα. Όλη αυτή η διαδικασία είναι η διαδικασία «Διαίρεση».

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

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

Επαναληπτική ταξινόμηση συγχώνευσης

Ο αλγόριθμος ή η τεχνική του είδους συγχώνευσης που έχουμε δει παραπάνω χρησιμοποιεί την αναδρομή. Είναι επίσης γνωστό ως « αναδρομική συγχώνευση '.

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

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

Όπως το είδος της αναδρομικής συγχώνευσης, το επαναλαμβανόμενο είδος συγχώνευσης έχει επίσης την πολυπλοκότητα O (nlogn) και συνεπώς την απόδοση σοφή, αποδίδουν στο ίδιο επίπεδο. Μπορούμε απλά να μειώσουμε τα γενικά έξοδα.

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

Δίνεται παρακάτω μια εφαρμογή τεχνικής συγχώνευσης με χρήση C ++.

#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray(i); } merge_sort(myarray, 0, num-1); cout<<'Sorted array '; for (int i = 0; i < num; i++) { cout<

Παραγωγή:

Εισαγάγετε τον αριθμό των στοιχείων που θα ταξινομηθούν: 10

Εισαγάγετε 10 στοιχεία προς ταξινόμηση: 101 10 2 43 12 54 34 64 89 76

Ταξινομημένος πίνακας

2 10 12 34 43 54 64 76 89 101

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

Στη συνέχεια, εφαρμόζουμε την τεχνική Merge Sort στη γλώσσα Java.

class MergeSort { void merge(int arr(), int beg, int mid, int end) { int left = mid - beg + 1; int right = end - mid; int Left_arr() = new int (left); int Right_arr() = new int (right); for (int i=0; i

Παραγωγή:

Σειρά εισαγωγής

101 10 2 43 12 54 34 64 89 76

Η σειρά ταξινομήθηκε χρησιμοποιώντας ταξινόμηση συγχώνευσης

2 10 12 34 43 54 64 76 89 101

Στην εφαρμογή Java επίσης, χρησιμοποιούμε την ίδια λογική που χρησιμοποιήσαμε στην υλοποίηση C ++.

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

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

Γνωρίζουμε ότι για να πραγματοποιήσουμε ταξινόμηση χρησιμοποιώντας συγχώνευση ταξινόμησης, πρώτα διαιρούμε τον πίνακα σε δύο ίσα μισά. Αυτό αντιπροσωπεύεται από το 'log n' που είναι μια λογαριθμική συνάρτηση και ο αριθμός των βημάτων που έχουν ληφθεί είναι το log (n + 1) το πολύ.

Στη συνέχεια για να βρούμε το μεσαίο στοιχείο του πίνακα απαιτούμε ένα μόνο βήμα, δηλαδή O (1).

Στη συνέχεια, για να συγχωνεύσουμε τις υπο-σειρές σε μια σειρά στοιχείων n, θα πάρουμε το O (n) χρόνο χρόνου εκτέλεσης.

Έτσι, ο συνολικός χρόνος για την εκτέλεση της ταξινόμησης συγχώνευσης θα είναι n (log n + 1), κάτι που μας δίνει την πολυπλοκότητα του χρόνου του O (n * logn).

Χειρότερη περίπτωση πολυπλοκότηταςO (n * log n)
Βέλτιστη πολυπλοκότητα χρόνουO (n * log n)
Μέσος χρόνος πολυπλοκότηταςO (n * log n)
Διαστημική πολυπλοκότηταΕπί)

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

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

συμπέρασμα

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

Η ταξινόμηση συγχώνευσης αποδίδει ταχύτερα από άλλες μεθόδους ταξινόμησης και λειτουργεί επίσης αποτελεσματικά για μικρότερες και μεγαλύτερες συστοιχίες.

Θα εξερευνήσουμε περισσότερα για τη Γρήγορη ταξινόμηση στο επερχόμενο σεμινάριο μας!

=> Παρακολουθήστε τον εκπαιδευτικό οδηγό για αρχάριους C ++ εδώ.

Συνιστώμενη ανάγνωση

^