En introduktion till Merge Sort Algorithm

Merge sort är en sorteringsalgoritm baserad på tekniken "dela och erövra". Det är en av de mest effektiva sorteringsalgoritmerna.

I den här artikeln får du lära dig mer om hur sorteringsalgoritmen fungerar, algoritmen för sammanslagningssorteringen, dess tids- och rymdkomplexitet och dess implementering på olika programmeringsspråk som C ++, Python och JavaScript.

Hur fungerar sammanslagningsalgoritmen?

Merge sort fungerar på principen om dela och erövra. Merge-sortering delar upp en grupp upprepade gånger i två lika subarrays tills varje subarray består av ett enda element. Slutligen slås alla dessa underarrayer samman så att den resulterande matrisen sorteras.

Detta koncept kan förklaras mer effektivt med hjälp av ett exempel. Tänk på en osorterad matris med följande element: {16, 12, 15, 13, 19, 17, 11, 18}.

Här delar algoritmen för sammanslagning upp matrisen i två halvor, kallar sig för de två halvorna och slår sedan samman de två sorterade halvorna.

Slå samman sorteringsalgoritm

Nedan följer algoritmen för sammanslagningssorteringen:

MergeSort (arr [], leftIndex, rightIndex)
om leftIndex> = rightIndex
lämna tillbaka
annan
Hitta mittindex som delar upp matrisen i två halvor: 
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
Ring mergeSort () under första halvåret: 
Call mergeSort (arr, leftIndex, middleIndex)
Ring mergeSort () för andra halvåret:
Call mergeSort (arr, middleIndex + 1, rightIndex)
Slå ihop de två halvorna sorterade i steg 2 och 3:
Samtalssamtal (arr, leftIndex, middleIndex, rightIndex)

Relaterad: Vad är rekursion och hur använder du det?

Tids- och rymdkomplexitet i Merge Sort Algorithm

Sorteringsalgoritmen kan uttryckas i form av följande återfallssamband:

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

Efter att ha löst denna återkommande relation med masterns teorem eller metoden för återkommande träd får du lösningen som O (n logn). Således är tidskomplexiteten hos algoritmen för sammanslagningssortering O (n logn).

Den bästa fallkomplexiteten för sammanslagningssorteringen: O (n logn)

Sammanfogningssorteringens genomsnittliga fallkomplexitet: O (n logn)

Den värsta fallskomplexiteten i sammanslagningssorten: O (n logn)

Relaterad: Vad är Big-O-notering?

Hjälputrymmets komplexitet av sammanslagningssorteringsalgoritmen är På) som n extra utrymme krävs vid implementering av sammanslagningssortering.

C ++ Implementering av Merge Sort Algorithm

Nedan följer C ++ implementeringen av algoritmen för sammanslagningssortering:

// C ++ implementering av
// sammanfoga sorteringsalgoritm
#omfatta 
använder namnrymd std;
// Denna funktion slår samman två underarrangemang av arr []
// Vänster subarray: arr [leftIndex..middleIndex]
// Höger subarray: arr [middleIndex + 1..rightIndex]
ogiltig sammanfogning (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Skapa tillfälliga matriser
int L [leftSubarraySize], R [rightSubarraySize];
// Kopiera data till tillfälliga matriser L [] och R []
för (int i = 0; i L [i] = arr [leftIndex + i];
för (int j = 0; j R [j] = arr [mittenIndex + 1 + j];
// Slå ihop de tillfälliga matriserna till arr [leftIndex..rightIndex]
// Initialt index för vänster subarray
int i = 0;
// Initialt index för höger subarray
int j = 0;
// Initialt index för sammanslagen undergrupp
int k = leftIndex;
medan (i {
om (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
annan
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Om det finns några kvarvarande element i L []
// Kopiera till arr []
medan (i {
arr [k] = L [i];
i ++;
k ++;
}
// Om det finns några kvarvarande element i R []
// Kopiera till arr []
medan (j {
arr [k] = R [j];
j ++;
k ++;
}
}
void mergeSort (int arr [], int leftIndex, int rightIndex)
{
om (leftIndex> = rightIndex)
{
lämna tillbaka;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
slå samman (arr, leftIndex, middleIndex, rightIndex);
}
// Funktion för att skriva ut elementen
// av matrisen
ogiltigt printArray (int arr [], int storlek)
{
för (int i = 0; i {
cout << arr [i] << "";
}
cout << endl;
}
// Förarkod
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int storlek = sizeof (arr) / sizeof (arr [0]);
cout << "Osorterad matris:" << endl;
printArray (arr, storlek);
mergeSort (arr, 0, storlek - 1);
cout << "Sorterad matris:" << endl;
printArray (arr, storlek);
returnera 0;
}

Produktion:

Osorterad matris:
16 12 15 13 19 17 11 18 
Sorterad matris:
11 12 13 15 16 17 18 19

JavaScript-implementering av Merge Sort Algorithm

Nedan följer JavaScript-implementeringen av algoritmen för sammanslagningssortering:

// JavaScript-implementering av
// sammanfoga sorteringsalgoritm
// Denna funktion slår samman två underarrangemang av arr []
// Vänster subarray: arr [leftIndex..middleIndex]
// Höger subarray: arr [middleIndex + 1..rightIndex]
funktionsfusion (arr, leftIndex, middleIndex, rightIndex) {
låt leftSubarraySize = middleIndex - leftIndex + 1;
låt rightSubarraySize = rightIndex - middleIndex;
// Skapa tillfälliga matriser
var L = ny matris (leftSubarraySize);
var R = ny matris (rightSubarraySize);
// Kopiera data till tillfälliga matriser L [] och R []
för (låt i = 0; iL [i] = arr [leftIndex + i];
}
för (låt j = 0; jR [j] = arr [mittenIndex + 1 + j];
}
// Slå ihop de tillfälliga matriserna till arr [leftIndex..rightIndex]
// Initialt index för vänster subarray
var i = 0;
// Initialt index för höger subarray
var j = 0;
// Initialt index för sammanslagen undergrupp
var k = leftIndex;
medan (i {
om (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
annan
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Om det finns några kvarvarande element i L []
// Kopiera till arr []
medan (i {
arr [k] = L [i];
i ++;
k ++;
}
// Om det finns några kvarvarande element i R []
// Kopiera till arr []
medan (j {
arr [k] = R [j];
j ++;
k ++;
}
}
funktion mergeSort (arr, leftIndex, rightIndex) {
om (leftIndex> = rightIndex) {
lämna tillbaka
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
slå samman (arr, leftIndex, middleIndex, rightIndex);
}
// Funktion för att skriva ut elementen
// av matrisen
funktion printArray (arr, storlek) {
för (låt i = 0; idocument.write (arr [i] + "");
}
document.write ("
");
}
// Förarkod:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var storlek = arrlängd;
document.write ("Osorterad matris:
");
printArray (arr, storlek);
mergeSort (arr, 0, storlek - 1);
document.write ("Sorterad matris:
");
printArray (arr, storlek);

Produktion:

Osorterad matris:
16 12 15 13 19 17 11 18
Sorterad matris:
11 12 13 15 16 17 18 19

Relaterad: Dynamisk programmering: Exempel, vanliga problem och lösningar

Python Implementation of the Merge Sort Algorithm

Nedan följer Python-implementeringen av algoritmen för sammanslagningssortering:

# Python-implementering av
# slå samman sorteringsalgoritm
def mergeSort (arr):
om len (arr)> 1:
# Hitta mittindex för matrisen
middleIndex = len (arr) // 2
# Vänster hälft av matrisen
L = arr [: middleIndex]
# Höger hälft av matrisen
R = arr [middleIndex:]
# Sorterar den första halvan av matrisen
mergeSort (L)
# Sortera andra halvan av matrisen
mergeSort (R)
# Initialt index för vänster subarray
i = 0
# Initialt index för höger subarray
j = 0
# Initialt index för sammanslagen undergrupp
k = 0
# Kopiera data till temp-matriserna L [] och R []
medan jag om L [i] arr [k] = L [i]
i = i + 1
annan:
arr [k] = R [j]
j = j + 1
k = k + 1
# Kontrollerar om det finns några kvarvarande element
medan jag arr [k] = L [i]
i = i + 1
k = k + 1
medan j arr [k] = R [j]
j = j + 1
k = k + 1
# Funktion för att skriva ut elementen
# av matrisen
def printArray (arr, storlek):
för jag inom intervallet (storlek):
skriva ut (arr [i], end = "")
skriva ut()
# Förarkod
arr = [16, 12, 15, 13, 19, 17, 11, 18]
storlek = len (arr)
skriv ut ("Osorterad matris:")
printArray (arr, storlek)
mergeSort (arr)
skriv ut ("Sorterad matris:")
printArray (arr, storlek)

Produktion:

Osorterad matris:
16 12 15 13 19 17 11 18
Sorterad matris:
11 12 13 15 16 17 18 19

Förstå andra sorteringsalgoritmer

Sortering är en av de mest använda algoritmerna vid programmering. Du kan sortera element på olika programmeringsspråk med hjälp av olika sorteringsalgoritmer som snabbsortering, bubblasortering, sammanslagningssortering, insättningssortering etc.

Bubblesortering är det bästa valet om du vill lära dig mer om den enklaste sorteringsalgoritmen.

En introduktion till bubblasorteringsalgoritmen

Bubble Sort-algoritmen: en utmärkt introduktion till sorteringsarrayer.

Läs Nästa

Om författaren