Een inleiding tot het samenvoegsorteeralgoritme

Merge sort is een sorteeralgoritme gebaseerd op de 'verdeel en heers'-techniek. Het is een van de meest efficiënte sorteeralgoritmen.

nep-telefoonnummer-app voor sms'en

In dit artikel leer je over de werking van het merge sort-algoritme, het algoritme van de merge sort, de complexiteit van tijd en ruimte en de implementatie ervan in verschillende programmeertalen zoals C++, Python en JavaScript.

---

---

Hoe werkt het samenvoegsorteeralgoritme?

Merge sort werkt volgens het principe van verdeel en heers. Samenvoegen sorteert herhaaldelijk een array in twee gelijke subarrays totdat elke subarray uit één enkel element bestaat. Ten slotte worden al die subarrays samengevoegd zodat de resulterende array wordt gesorteerd.

Dit concept kan efficiënter worden uitgelegd aan de hand van een voorbeeld. Beschouw een ongesorteerde array met de volgende elementen: {16, 12, 15, 13, 19, 17, 11, 18}.

Hier verdeelt het sorteeralgoritme voor samenvoegen de array in twee helften, roept zichzelf op voor de twee helften en voegt vervolgens de twee gesorteerde helften samen.

Sorteeralgoritme samenvoegen

Hieronder staat het algoritme van de merge sort:

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)

Verwant: Wat is recursie en hoe gebruik je het?

---

---

Tijd- en ruimtecomplexiteit van het samenvoegsorteeralgoritme

Het sorteeralgoritme samenvoegen kan worden uitgedrukt in de vorm van de volgende herhalingsrelatie:

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

---

---

Na het oplossen van deze recursierelatie met behulp van de stelling van de meester of de recursieboommethode, krijg je de oplossing als O(n logn). De tijdscomplexiteit van het samenvoegsorteeralgoritme is dus: O (n log) .

De beste tijdcomplexiteit van de samenvoegsoort: O (n log)

De gemiddelde tijdscomplexiteit van de samenvoegsoort: O (n log)

De slechtste tijdscomplexiteit van de samenvoegsoort: O (n log)

Verwant: Wat is Big-O-notatie?

De complexiteit van de hulpruimte van het merge sort algoritme is Op) als N extra ruimte is vereist in de implementatie van merge sort.

C++ Implementatie van het Merge Sort Algoritme

Hieronder staat de C++-implementatie van het merge sort-algoritme:

// 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;
}

Uitgang:

Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19

JavaScript-implementatie van het samenvoegsorteeralgoritme

Hieronder staat de JavaScript-implementatie van het merge sort-algoritme:

// 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);

Uitgang:

Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19

Gerelateerd: Dynamisch programmeren: voorbeelden, veelvoorkomende problemen en oplossingen

Python-implementatie van het samenvoegsorteeralgoritme

Hieronder staat de Python-implementatie van het merge sort-algoritme:

# 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)


Uitgang:

Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19

Andere sorteeralgoritmen begrijpen

Sorteren is een van de meest gebruikte algoritmen bij het programmeren. U kunt elementen in verschillende programmeertalen sorteren met behulp van verschillende sorteeralgoritmen zoals snel sorteren, bellensorteren, samenvoegen sorteren, invoegen sorteren, enz.

Bellen sorteren is de beste keuze als u meer wilt weten over het eenvoudigste sorteeralgoritme.

Deel Deel Tweeten E-mail Een inleiding tot het bellensorteeralgoritme

Het Bubble Sort-algoritme: een uitstekende introductie tot het sorteren van arrays.

Lees volgende Gerelateerde onderwerpen

• Programmeren
• JavaScript
• Python
• Codeerhandleidingen

Over de auteur Yuvraj Chandra(60 artikelen gepubliceerd)

Yuvraj is een student Computerwetenschappen aan de Universiteit van Delhi, India. Hij is gepassioneerd door Full Stack Web Development. Als hij niet aan het schrijven is, onderzoekt hij de diepte van verschillende technologieën.

Meer van Yuvraj Chandra

Abonneer op onze nieuwsbrief

Word lid van onze nieuwsbrief voor technische tips, recensies, gratis e-boeken en exclusieve deals!

Klik hier om je te abonneren