Εισαγωγή στον αλγόριθμο συγχώνευσης ταξινόμησης

Το Merge sort είναι ένας αλγόριθμος ταξινόμησης που βασίζεται στην τεχνική "διαίρεση και κατάκτηση". Είναι ένας από τους πιο αποτελεσματικούς αλγόριθμους ταξινόμησης.

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

Πώς λειτουργεί ο αλγόριθμος συγχώνευσης ταξινόμησης;

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

Αυτή η ιδέα μπορεί να εξηγηθεί πιο αποτελεσματικά με τη βοήθεια ενός παραδείγματος. Εξετάστε έναν μη ταξινομημένο πίνακα με τα ακόλουθα στοιχεία: {16, 12, 15, 13, 19, 17, 11, 18}.

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

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

Παρακάτω είναι ο αλγόριθμος του είδους συγχώνευσης:

MergeSort (arr [], leftIndex, rightIndex)
εάν leftIndex> = rightIndex
ΕΠΙΣΤΡΟΦΗ
αλλού
Βρείτε το μεσαίο ευρετήριο που χωρίζει τον πίνακα σε δύο μισά: 
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
Κλήση mergeSort () για το πρώτο ημίχρονο: 
Κλήση mergeSort (arr, leftIndex, middleIndex)
Καλέστε το mergeSort () για το δεύτερο ημίχρονο:
Κλήση mergeSort (arr, middleIndex + 1, rightIndex)
Συγχωνεύστε τα δύο μισά που ταξινομούνται στα βήματα 2 και 3:
Συγχώνευση κλήσης (arr, leftIndex, middleIndex, rightIndex)

Σχετιζομαι με: Τι είναι η αναδρομή και πώς τη χρησιμοποιείτε;

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

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

T (n) = 2T (n / 2) + O (n)

Αφού επιλύσετε αυτήν τη σχέση επανάληψης χρησιμοποιώντας το θεώρημα του πλοιάρχου ή τη μέθοδο δέντρου υποτροπής, θα λάβετε τη λύση ως O (n logn). Έτσι, η χρονική πολυπλοκότητα του αλγορίθμου ταξινόμησης συγχώνευσης είναι O (n logn).

Η καλύτερη χρονική πολυπλοκότητα του είδους συγχώνευσης: O (n logn)

Η πολυπλοκότητα του μέσου χρόνου για το είδος της συγχώνευσης: O (n logn)

Η χειρότερη περίπτωση πολυπλοκότητας του είδους συγχώνευσης: O (n logn)

Σχετιζομαι με: Τι είναι η σημείωση Big-O;

Η πολυπλοκότητα του βοηθητικού χώρου είναι ο αλγόριθμος συγχώνευσης Επί) όπως και ν Απαιτείται βοηθητικός χώρος στην εφαρμογή ταξινόμησης συγχώνευσης.

C ++ Εφαρμογή του Αλγόριθμου Συγχώνευσης Ταξινόμησης

Ακολουθεί η εφαρμογή C ++ του αλγορίθμου ταξινόμησης συγχώνευσης:

// C ++ εφαρμογή του
// συγχώνευση αλγορίθμου ταξινόμησης
#περιλαμβάνω 
χρησιμοποιώντας το namespace std;
// Αυτή η συνάρτηση συγχωνεύει δύο subarrays του arr []
// Αριστερή υποπεριοχή: arr [leftIndex..middleIndex]
// Δεξιά δευτερεύουσα σειρά: arr [middleIndex + 1..rightIndex]
άκυρη συγχώνευση (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Δημιουργήστε προσωρινές συστοιχίες
int L [leftSubarraySize], R [rightSubarraySize];
// Αντιγραφή δεδομένων σε προσωρινές συστοιχίες L [] και R []
για (int i = 0; εγώ L [i] = arr [αριστεράIndex + i];
για (int j = 0; j R [j] = arr [middleIndex + 1 + j];
// Συγχώνευση των προσωρινών συστοιχιών πίσω στο arr [leftIndex..rightIndex]
// Αρχικός δείκτης της Αριστεράς υποπεριοχής
int i = 0;
// Αρχικός δείκτης Δεξιού δευτερεύοντος εδάφους
int j = 0;
// Αρχικός δείκτης συγχωνευμένης υποπεριοχής
int k = leftIndex;
ενώ (i {
αν (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
αλλού
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Εάν υπάρχουν κάποια υπόλοιπα στοιχεία στο L []
// Αντιγραφή στο arr []
ενώ (i {
arr [k] = L [i];
i ++;
k ++;
}
// Εάν υπάρχουν κάποια υπόλοιπα στοιχεία στο R []
// Αντιγραφή στο arr []
ενώ (j {
arr [k] = R [j];
j ++;
k ++;
}
}
void mergeSort (int arr [], int leftIndex, int rightIndex)
{
εάν (leftIndex> = rightIndex)
{
ΕΠΙΣΤΡΟΦΗ;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
συγχώνευση (arr, leftIndex, middleIndex, rightIndex);
}
// Λειτουργία εκτύπωσης των στοιχείων
// του πίνακα
void printArray (int arr [], int μέγεθος)
{
για (int i = 0; {
<< arr [i] << "";
}
cout << endl;
}
// Κωδικός προγράμματος οδήγησης
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int size = sizeof (arr) / sizeof (arr [0]);
cout << "Χωρίς ταξινόμηση πίνακα:" << endl;
printArray (arr, μέγεθος);
mergeSort (arr, 0, μέγεθος - 1);
cout << "Ταξινομημένος πίνακας:" << endl;
printArray (arr, μέγεθος);
επιστροφή 0;
}

Παραγωγή:

Μη ταξινομημένος πίνακας:
16 12 15 13 19 17 11 18 
Ταξινομημένος πίνακας:
11 12 13 15 16 17 18 19

Εφαρμογή JavaScript του αλγόριθμου συγχώνευσης ταξινόμησης

Ακολουθεί η εφαρμογή JavaScript του αλγορίθμου ταξινόμησης συγχώνευσης:

// Εφαρμογή JavaScript του
// συγχώνευση αλγορίθμου ταξινόμησης
// Αυτή η συνάρτηση συγχωνεύει δύο subarrays του arr []
// Αριστερή υποπεριοχή: arr [leftIndex..middleIndex]
// Δεξιά δευτερεύουσα σειρά: arr [middleIndex + 1..rightIndex]
συγχώνευση συνάρτησης (arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
// Δημιουργήστε προσωρινές συστοιχίες
var L = νέο Array (leftSubarraySize);
var R = νέο Array (rightSubarraySize);
// Αντιγραφή δεδομένων σε προσωρινές συστοιχίες L [] και R []
για (let i = 0; ΕγώL [i] = arr [αριστεράIndex + i];
}
για (ας j = 0; ιR [j] = arr [middleIndex + 1 + j];
}
// Συγχώνευση των προσωρινών συστοιχιών πίσω στο arr [leftIndex..rightIndex]
// Αρχικός δείκτης της Αριστεράς υποπεριοχής
var i = 0;
// Αρχικός δείκτης Δεξιού δευτερεύοντος εδάφους
var j = 0;
// Αρχικός δείκτης συγχωνευμένης υποπεριοχής
var k = leftIndex;
ενώ (i {
αν (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
αλλού
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Εάν υπάρχουν κάποια υπόλοιπα στοιχεία στο L []
// Αντιγραφή στο arr []
ενώ (i {
arr [k] = L [i];
i ++;
k ++;
}
// Εάν υπάρχουν κάποια υπόλοιπα στοιχεία στο R []
// Αντιγραφή στο arr []
ενώ (j {
arr [k] = R [j];
j ++;
k ++;
}
}
συνάρτηση mergeSort (arr, leftIndex, rightIndex) {
εάν (leftIndex> = rightIndex) {
ΕΠΙΣΤΡΟΦΗ
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
συγχώνευση (arr, leftIndex, middleIndex, rightIndex);
}
// Λειτουργία εκτύπωσης των στοιχείων
// του πίνακα
function printArray (arr, μέγεθος) {
για (let i = 0; Εγώdocument.write (arr [i] + "");
}
document.write ("
");
}
// Κωδικός προγράμματος οδήγησης:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var size = arr.length;
document.write ("Χωρίς ταξινόμηση πίνακα:
");
printArray (arr, μέγεθος);
mergeSort (arr, 0, μέγεθος - 1);
document.write ("Ταξινομημένος πίνακας:
");
printArray (arr, μέγεθος);

Παραγωγή:

Μη ταξινομημένος πίνακας:
16 12 15 13 19 17 11 18
Ταξινομημένος πίνακας:
11 12 13 15 16 17 18 19

Σχετιζομαι με: Δυναμικός προγραμματισμός: Παραδείγματα, κοινά προβλήματα και λύσεις

Εφαρμογή του αλγόριθμου συγχώνευσης Python

Ακολουθεί η εφαρμογή Python του αλγορίθμου ταξινόμησης συγχώνευσης:

# Εφαρμογή Python του
# αλγόριθμος συγχώνευσης ταξινόμησης
def mergeSort (arr):
εάν len (arr)> 1:
# Εύρεση του μεσαίου ευρετηρίου του πίνακα
middleIndex = len (arr) // 2
# Αριστερό μισό του πίνακα
L = arr [: middleIndex]
# Δεξί μισός του πίνακα
R = arr [middleIndex:]
# Ταξινόμηση του πρώτου μισού του πίνακα
mergeSort (Λ)
# Ταξινόμηση του δεύτερου μισού του πίνακα
mergeSort (R)
# Αρχικός δείκτης της αριστερής υποπεριοχής
i = 0
# Αρχικός δείκτης Δεξιού δευτερεύοντος εδάφους
j = 0
# Αρχικός δείκτης συγχωνευμένης υποπεριοχής
k = 0
# Αντιγραφή δεδομένων σε πίνακες temp L [] και R []
ενώ είμαι αν L [i] arr [k] = L [i]
i = i + 1
αλλού:
arr [k] = R [j]
j = j + 1
k = k + 1
# Έλεγχος εάν υπάρχουν κάποια στοιχεία που απομένουν
ενώ εγώ arr [k] = L [i]
i = i + 1
k = k + 1
ενώ j arr [k] = R [j]
j = j + 1
k = k + 1
# Λειτουργία εκτύπωσης των στοιχείων
# του πίνακα
def printArray (arr, μέγεθος):
για i in range (μέγεθος):
εκτύπωση (arr [i], end = "")
Τυπώνω()
# Κωδικός προγράμματος οδήγησης
arr = [16, 12, 15, 13, 19, 17, 11, 18]
μέγεθος = len (arr)
εκτύπωση ("Μη ταξινομημένος πίνακας:")
printArray (arr, μέγεθος)
mergeSort (arr)
εκτύπωση ("Ταξινομημένος πίνακας:")
printArray (arr, μέγεθος)

Παραγωγή:

Μη ταξινομημένος πίνακας:
16 12 15 13 19 17 11 18
Ταξινομημένος πίνακας:
11 12 13 15 16 17 18 19

Κατανόηση άλλων αλγορίθμων ταξινόμησης

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

Το Bubble sort είναι η καλύτερη επιλογή αν θέλετε να μάθετε για τον απλούστερο αλγόριθμο ταξινόμησης.

Εισαγωγή στον αλγόριθμο Bubble Sort

Ο αλγόριθμος Bubble Sort: μια εξαιρετική εισαγωγή στη σειρά ταξινόμησης.

Διαβάστε Επόμενο

Σχετικά με τον Συγγραφέα