Een inleiding tot het samenvoegsorteeralgoritme

Samenvoegen sorteren is een sorteeralgoritme gebaseerd op de "verdeel en heers"-techniek. Het is een van de meest efficiënte sorteeralgoritmen.

In dit artikel leer je over de werking van het merge sort algoritme, het algoritme van de merge sort, zijn tijd- en ruimtecomplexiteit, 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
terugkeer
anders
Zoek de middelste index die de array in twee helften verdeelt: 
middleIndex = leftIndex + (rightIndex-leftIndex)/2
Roep mergeSort() aan voor de eerste helft: 
Roep mergeSort aan (arr, leftIndex, middleIndex)
Roep mergeSort() aan voor de tweede helft:
Roep mergeSort aan (arr, middleIndex+1, rightIndex)
Voeg de twee helften samen die in stap 2 en 3 zijn gesorteerd:
Oproep samenvoegen (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 Aan) net zo nee 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++ implementatie van de
// sorteeralgoritme samenvoegen
#include 
namespace std; gebruiken;
// Deze functie voegt twee subarrays van arr[] samen
// Linker subarray: arr [leftIndex..middleIndex]
// Rechter subarray: arr[middleIndex+1..rightIndex]
void merge (int arr[], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Maak tijdelijke arrays
int L[leftSubarraySize], R[rightSubarraySize];
// Gegevens kopiëren naar tijdelijke arrays L[] en R[]
voor (int i = 0; i < leftSubarraySize; ik++)
L[i] = arr[leftIndex + i];
voor (int j = 0; j < rightSubarraySize; j++)
R[j] = arr[middleIndex + 1 + j];
// Voeg de tijdelijke arrays weer samen in arr [leftIndex..rightIndex]
// Initiële index van linker subarray
int ik = 0;
// Initiële index van rechter subarray
intj = 0;
// Initiële index van samengevoegde subarray
int k = linkerIndex;
while (i < leftSubarraySize && j < rightSubarraySize)
{
als (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
anders
{
arr[k] = R[j];
j++;
}
k++;
}
// Als er nog enkele elementen in L []
// Kopieer naar arr[]
while (i < leftSubarraySize)
{
arr[k] = L[i];
i++;
k++;
}
// Als er nog enkele elementen in R []
// Kopieer naar arr[]
while (j < rightSubarraySize)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort (int arr[], int leftIndex, int rightIndex)
{
if (leftIndex >= rightIndex)
{
terugkeer;
}
int middleIndex = leftIndex + (rightIndex - leftIndex)/2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex+1, rightIndex);
samenvoegen (arr, leftIndex, middleIndex, rightIndex);
}
// Functie om de elementen af ​​te drukken
// van de array
void printArray (int arr[], int size)
{
voor (int i = 0; ik < maat; ik++)
{
cout << arr[i] << " ";
}
cout << endl;
}
// Bestuurderscode
int hoofd()
{
int arr[] = { 16, 12, 15, 13, 19, 17, 11, 18 };
int size = sizeof (arr) / sizeof (arr[0]);
cout << "Ongesorteerde array:" << endl;
printArray (arr, grootte);
mergeSort (arr, 0, grootte - 1);
cout << "Gesorteerde array:" << endl;
printArray (arr, grootte);
retourneer 0;
}

Uitgang:

Ongesorteerde reeks:
16 12 15 13 19 17 11 18 
Gesorteerde reeks:
11 12 13 15 16 17 18 19

JavaScript-implementatie van het samenvoegsorteeralgoritme

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

// JavaScript-implementatie van de
// sorteeralgoritme samenvoegen
// Deze functie voegt twee subarrays van arr[] samen
// Linker subarray: arr [leftIndex..middleIndex]
// Rechter subarray: arr[middleIndex+1..rightIndex]
functie samenvoegen (arr, leftIndex, middleIndex, rightIndex) {
laat leftSubarraySize = middleIndex - leftIndex + 1;
laat rightSubarraySize = rightIndex - middleIndex;
// Maak tijdelijke arrays
var L = nieuwe array (leftSubarraySize);
var R = nieuwe array (rightSubarraySize);
// Gegevens kopiëren naar tijdelijke arrays L[] en R[]
voor (laat ik = 0; ikL[i] = arr[leftIndex + i];
}
voor (laat j = 0; jR[j] = arr[middleIndex + 1 + j];
}
// Voeg de tijdelijke arrays weer samen in arr [leftIndex..rightIndex]
// Initiële index van linker subarray
var i = 0;
// Initiële index van rechter subarray
var j = 0;
// Initiële index van samengevoegde subarray
var k = linkerindex;
while (i < leftSubarraySize && j < rightSubarraySize)
{
als (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
anders
{
arr[k] = R[j];
j++;
}
k++;
}
// Als er nog enkele elementen in L []
// Kopieer naar arr[]
while (i < leftSubarraySize)
{
arr[k] = L[i];
i++;
k++;
}
// Als er nog enkele elementen in R []
// Kopieer naar arr[]
while (j < rightSubarraySize)
{
arr[k] = R[j];
j++;
k++;
}
}
functie mergeSort (arr, leftIndex, rightIndex) {
if (leftIndex >= rightIndex) {
terugkeer
}
var middleIndex = leftIndex + parseInt((rightIndex - leftIndex)/2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex+1, rightIndex);
samenvoegen (arr, leftIndex, middleIndex, rightIndex);
}
// Functie om de elementen af ​​te drukken
// van de array
functie printArray (arr, grootte) {
voor (laat ik = 0; ikdocument.schrijven (arr[i] + " ");
}
document.schrijven("
");
}
// Bestuurderscode:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var grootte = arr.lengte;
document.write("Ongesorteerde array:
");
printArray (arr, grootte);
mergeSort (arr, 0, grootte - 1);
document.write("Gesorteerde array:
");
printArray (arr, grootte);

Uitgang:

Ongesorteerde reeks:
16 12 15 13 19 17 11 18
Gesorteerde reeks:
11 12 13 15 16 17 18 19

Verwant: Dynamisch programmeren: voorbeelden, veelvoorkomende problemen en oplossingen

Python-implementatie van het samenvoegsorteeralgoritme

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

# Python-implementatie van de
# sorteeralgoritme samenvoegen
def mergeSort (arr):
als len (arr) > 1:
# De middelste index van de array vinden
middleIndex = len (arr)//2
# Linkerhelft van de array
L = arr[:middleIndex]
# Rechter helft van de array
R = arr[middleIndex:]
# Sorteren van de eerste helft van de array
samenvoegenSorteren (L)
# Sorteren van de tweede helft van de array
samenvoegenSorteren (R)
# Initiële index van linker subarray
ik = 0
# Initiële index van rechter subarray
j = 0
# Initiële index van samengevoegde subarray
k = 0
# Kopieer gegevens naar tijdelijke arrays L[] en R[]
terwijl i < len (L) en j < len (R):
als L[i] < R[j]:
arr[k] = L[i]
ik = ik + 1
anders:
arr[k] = R[j]
j = j + 1
k = k + 1
# Controleren of er nog elementen over zijn
terwijl ik < len (L):
arr[k] = L[i]
ik = ik + 1
k = k + 1
terwijl j arr[k] = R[j]
j = j + 1
k = k + 1
# Functie om de elementen af ​​te drukken
# van de array
def printArray (arr, grootte):
voor i binnen bereik (maat):
print (arr[i], end=" ")
afdrukken()
# Bestuurderscode
arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ]
maat = len (arr)
print("Ongesorteerde array:")
printArray (arr, grootte)
samenvoegenSorteren (arr)
print("Gesorteerde matrix:")
printArray (arr, grootte)

Uitgang:

Ongesorteerde reeks:
16 12 15 13 19 17 11 18
Gesorteerde reeks:
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.

Een inleiding tot het bellensorteeralgoritme

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

Lees volgende

Over de auteur