Home-theater-designers
Η συγχώνευση ταξινόμησης είναι ένας αλγόριθμος ταξινόμησης που βασίζεται στην τεχνική «διαίρει και κατέκτησε». Είναι ένας από τους πιο αποτελεσματικούς αλγόριθμους ταξινόμησης.
καθρέφτης οθόνης android στον υπολογιστή ασύρματα
Σε αυτό το άρθρο, θα μάθετε για τη λειτουργία του αλγορίθμου ταξινόμησης συγχώνευσης, τον αλγόριθμο της ταξινόμησης συγχώνευσης, την πολυπλοκότητα του χρόνου και του χώρου και την εφαρμογή του σε διάφορες γλώσσες προγραμματισμού όπως C ++, Python και JavaScript.
Πώς λειτουργεί ο αλγόριθμος συγχώνευσης ταξινόμησης;
Η συγχώνευση ταξινόμησης λειτουργεί με την αρχή του διαίρει και κατακτά. Η συγχώνευση ταξινόμησης αναλύει επανειλημμένα έναν πίνακα σε δύο ίσες υποσυστοιχίες έως ότου κάθε υποσυστοιχία αποτελείται από ένα μόνο στοιχείο. Τέλος, όλες αυτές οι υποσυστοιχίες συγχωνεύονται έτσι ώστε ο πίνακας που προκύπτει να ταξινομείται.
Αυτή η έννοια μπορεί να εξηγηθεί πιο αποτελεσματικά με τη βοήθεια ενός παραδείγματος. Εξετάστε έναν πίνακα χωρίς ταξινόμηση με τα ακόλουθα στοιχεία: {16, 12, 15, 13, 19, 17, 11, 18}.
Εδώ, ο αλγόριθμος συγχώνευσης ταξινόμησης χωρίζει τον πίνακα σε δύο μισά, καλεί τον εαυτό του για τα δύο μισά και στη συνέχεια συγχωνεύει τα δύο ταξινομημένα μισά.
Αλγόριθμος συγχώνευσης ταξινόμησης
Παρακάτω είναι ο αλγόριθμος της ταξινόμησης συγχώνευσης:
MergeSort(arr[], leftIndex, rightIndex)
if leftIndex >= rightIndex
return
else
Find the middle index that divides the array into two halves:
middleIndex = leftIndex + (rightIndex-leftIndex)/2
Call mergeSort() for the first half:
Call mergeSort(arr, leftIndex, middleIndex)
Call mergeSort() for the second half:
Call mergeSort(arr, middleIndex+1, rightIndex)
Merge the two halves sorted in step 2 and 3:
Call merge(arr, leftIndex, middleIndex, rightIndex)Σχετικά: Τι είναι το Recursion και πώς το χρησιμοποιείτε;
Πολυπλοκότητα χρόνου και χώρου του αλγορίθμου ταξινόμησης συγχώνευσης
Ο αλγόριθμος ταξινόμησης συγχώνευσης μπορεί να εκφραστεί με τη μορφή της ακόλουθης σχέσης υποτροπής:
T (n) = 2T (n / 2) + O (n)
Αφού λύσετε αυτήν τη σχέση υποτροπής χρησιμοποιώντας το κύριο θεώρημα ή τη μέθοδο δέντρου επανάληψης, θα λάβετε τη λύση ως O (n logn). Έτσι, η χρονική πολυπλοκότητα του αλγορίθμου ταξινόμησης συγχώνευσης είναι O (n logn) Το
Η περίπλοκη χρονική περίπτωση της κατηγορίας συγχώνευσης: O (n logn)
Η μέση περίπλοκη χρονική πολυπλοκότητα της ταξινόμησης συγχώνευσης: O (n logn)
Η χειρότερη περίπλοκη χρονική πολυπλοκότητα του είδους συγχώνευσης: O (n logn)
Σχετίζεται με: Τι είναι το Big-O Notation;
Η πολυπλοκότητα του βοηθητικού χώρου του αλγορίθμου ταξινόμησης συγχώνευσης είναι Επί) όπως και ν απαιτείται βοηθητικός χώρος στην υλοποίηση ταξινόμησης συγχώνευσης.
Υλοποίηση C ++ του αλγορίθμου συγχώνευσης ταξινόμησης
Παρακάτω είναι η εφαρμογή C ++ του αλγορίθμου ταξινόμησης συγχώνευσης:
// C++ implementation of the
// merge sort algorithm
#include
using namespace std;
// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
void merge(int arr[], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Create temporary arrays
int L[leftSubarraySize], R[rightSubarraySize];
// Copying data to temporary arrays L[] and R[]
for (int i = 0; i L[i] = arr[leftIndex + i];
for (int j = 0; j R[j] = arr[middleIndex + 1 + j];
// Merge the temporary arrays back into arr[leftIndex..rightIndex]
// Initial index of Left subarray
int i = 0;
// Initial index of Right subarray
int j = 0;
// Initial index of merged subarray
int k = leftIndex;
while (i {
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// If there're some remaining elements in L[]
// Copy to arr[]
while (i {
arr[k] = L[i];
i++;
k++;
}
// If there're some remaining elements in R[]
// Copy to arr[]
while (j {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int leftIndex, int rightIndex)
{
if(leftIndex >= rightIndex)
{
return;
}
int middleIndex = leftIndex + (rightIndex - leftIndex)/2;
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}
// Function to print the elements
// of the array
void printArray(int arr[], int size)
{
for (int i = 0; i {
cout << arr[i] << ' ';
}
cout << endl;
}
// Driver code
int main()
{
int arr[] = { 16, 12, 15, 13, 19, 17, 11, 18 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << 'Unsorted array:' << endl;
printArray(arr, size);
mergeSort(arr, 0, size - 1);
cout << 'Sorted array:' << endl;
printArray(arr, size);
return 0;
} Παραγωγή:
Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19Εφαρμογή JavaScript του αλγορίθμου ταξινόμησης συγχώνευσης
Παρακάτω είναι η υλοποίηση JavaScript του αλγορίθμου ταξινόμησης συγχώνευσης:
// JavaScript implementation of the
// merge sort algorithm
// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
function merge(arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
// Create temporary arrays
var L = new Array(leftSubarraySize);
var R = new Array(rightSubarraySize);
// Copying data to temporary arrays L[] and R[]
for(let i = 0; i L[i] = arr[leftIndex + i];
}
for (let j = 0; j R[j] = arr[middleIndex + 1 + j];
}
// Merge the temporary arrays back into arr[leftIndex..rightIndex]
// Initial index of Left subarray
var i = 0;
// Initial index of Right subarray
var j = 0;
// Initial index of merged subarray
var k = leftIndex;
while (i {
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// If there're some remaining elements in L[]
// Copy to arr[]
while (i {
arr[k] = L[i];
i++;
k++;
}
// If there're some remaining elements in R[]
// Copy to arr[]
while (j {
arr[k] = R[j];
j++;
k++;
}
}
function mergeSort(arr, leftIndex, rightIndex) {
if(leftIndex >= rightIndex) {
return
}
var middleIndex = leftIndex + parseInt((rightIndex - leftIndex)/2);
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}
// Function to print the elements
// of the array
function printArray(arr, size) {
for(let i = 0; i document.write(arr[i] + ' ');
}
document.write('
');
}
// Driver code:
var arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ];
var size = arr.length;
document.write('Unsorted array:
');
printArray(arr, size);
mergeSort(arr, 0, size - 1);
document.write('Sorted array:
');
printArray(arr, size); Παραγωγή:
Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19Σχετικά: Δυναμικός προγραμματισμός: Παραδείγματα, κοινά προβλήματα και λύσεις
Υλοποίηση Python του αλγορίθμου ταξινόμησης συγχώνευσης
Παρακάτω είναι η εφαρμογή Python του αλγορίθμου ταξινόμησης συγχώνευσης:
# Python implementation of the
# merge sort algorithm
def mergeSort(arr):
if len(arr) > 1:
# Finding the middle index of the array
middleIndex = len(arr)//2
# Left half of the array
L = arr[:middleIndex]
# Right half of the array
R = arr[middleIndex:]
# Sorting the first half of the array
mergeSort(L)
# Sorting the second half of the array
mergeSort(R)
# Initial index of Left subarray
i = 0
# Initial index of Right subarray
j = 0
# Initial index of merged subarray
k = 0
# Copy data to temp arrays L[] and R[]
while i if L[i] arr[k] = L[i]
i = i + 1
else:
arr[k] = R[j]
j = j + 1
k = k + 1
# Checking if there're some remaining elements
while i arr[k] = L[i]
i = i + 1
k = k + 1
while j arr[k] = R[j]
j = j + 1
k = k + 1
# Function to print the elements
# of the array
def printArray(arr, size):
for i in range(size):
print(arr[i], end=' ')
print()
# Driver code
arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ]
size = len(arr)
print('Unsorted array:')
printArray(arr, size)
mergeSort(arr)
print('Sorted array:')
printArray(arr, size)
Παραγωγή:
Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19Κατανόηση άλλων αλγορίθμων ταξινόμησης
Η ταξινόμηση είναι ένας από τους πιο χρησιμοποιούμενους αλγόριθμους στον προγραμματισμό. Μπορείτε να ταξινομήσετε στοιχεία σε διαφορετικές γλώσσες προγραμματισμού χρησιμοποιώντας διάφορους αλγόριθμους ταξινόμησης όπως γρήγορη ταξινόμηση, ταξινόμηση φυσαλίδων, ταξινόμηση συγχώνευσης, ταξινόμηση εισαγωγής κ.λπ.
Η ταξινόμηση φυσαλίδων είναι η καλύτερη επιλογή εάν θέλετε να μάθετε για τον απλούστερο αλγόριθμο ταξινόμησης.
Μερίδιο Μερίδιο Τιτίβισμα ΗΛΕΚΤΡΟΝΙΚΗ ΔΙΕΥΘΥΝΣΗ Εισαγωγή στον αλγόριθμο ταξινόμησης φυσαλίδωνΟ αλγόριθμος Bubble Sort: μια εξαιρετική εισαγωγή στη διαλογή συστοιχιών.
Διαβάστε Επόμενο Σχετικά θέματα- Προγραμματισμός
- JavaScript
- Πύθων
- Φροντιστήρια κωδικοποίησης
Ο Yuvraj είναι προπτυχιακός φοιτητής Πληροφορικής στο Πανεπιστήμιο του Δελχί, Ινδία. Είναι παθιασμένος με το Full Stack Web Development. Όταν δεν γράφει, εξερευνά το βάθος διαφορετικών τεχνολογιών.
Περισσότερα από τον Yuvraj ChandraΕγγραφείτε στο newsletter μας
Εγγραφείτε στο ενημερωτικό μας δελτίο για τεχνικές συμβουλές, κριτικές, δωρεάν ebooks και αποκλειστικές προσφορές!
Κάντε κλικ εδώ για εγγραφή