En introduksjon til Merge Sort Algorithm

Merge sort er en sorteringsalgoritme basert på "divide and conquer" -teknikken. Det er en av de mest effektive sorteringsalgoritmene.

I denne artikkelen vil du lære om hvordan algoritmen for sammenslåingssortering fungerer, algoritmen for sammenslåingssorteringen, dens tid og romkompleksitet, og implementeringen av den i forskjellige programmeringsspråk som C ++, Python og JavaScript.

Hvordan fungerer Merge Sort Algorithm?

Merge sort fungerer på prinsippet om å dele og erobre. Merge sort bryter en rekke gjentatte ganger ned i to like underarrays til hvert subarray består av et enkelt element. Til slutt blir alle disse underarrangene slått sammen slik at den resulterende matrisen blir sortert.

Dette konseptet kan forklares mer effektivt ved hjelp av et eksempel. Vurder en usortert matrise med følgende elementer: {16, 12, 15, 13, 19, 17, 11, 18}.

Her deler algoritmen for flettesortering matrisen i to halvdeler, kaller seg for de to halvdelene, og slår deretter sammen de to sorterte halvdelene.

Slå sammen sorteringsalgoritme

Nedenfor er algoritmen for sammenslåingssorteringen:

MergeSort (arr [], leftIndex, rightIndex)
hvis leftIndex> = rightIndex
komme tilbake
ellers
Finn den midtre indeksen som deler matrisen i to halvdeler: 
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
Ring mergeSort () for første omgang: 
Call mergeSort (arr, leftIndex, middleIndex)
Call mergeSort () for andre omgang:
Call mergeSort (arr, middleIndex + 1, rightIndex)
Slå sammen de to halvdelene sortert i trinn 2 og 3:
Slå sammen (arr, leftIndex, middleIndex, rightIndex)

I slekt: Hva er rekursjon og hvordan bruker du det?

Tid og romkompleksitet av Merge Sort Algorithm

Algoritmen for sorteringssortering kan uttrykkes i form av følgende gjentakelsesrelasjon:

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

Etter å ha løst dette gjentakelsesforholdet ved å bruke mastersetningen eller metoden for gjentakelsestre, får du løsningen som O (n logn). Dermed er tidskompleksiteten til flersorteringsalgoritmen O (n logn).

Beste tilfelle tidskompleksitet av sammenslåingssorteringen: O (n logn)

Gjennomsnittlig tidskompleksitet for sammenslåingssorteringen: O (n logn)

Den mest tilfeldige tidskompleksiteten til sammenslåingssorten: O (n logn)

I slekt: Hva er Big-O-notasjon?

Hjelpeplasskompleksiteten av sammenslåingssorteringsalgoritmen er På) som n det er behov for ekstra plass i implementeringen av sammenslåingen.

C ++ Implementering av Merge Sort Algorithm

Nedenfor er C ++ implementeringen av flersorteringsalgoritmen:

// C ++ implementering av
// flette sorteringsalgoritme
#inkludere 
bruker navneområde std;
// Denne funksjonen slår sammen to underarrayer av arr []
// Venstre subarray: arr [leftIndex..middleIndex]
// Høyre undergruppe: arr [middleIndex + 1..rightIndex]
ugyldig sammenslåing (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Lag midlertidige matriser
int L [leftSubarraySize], R [rightSubarraySize];
// Kopiere data til midlertidige matriser L [] og R []
for (int i = 0; i L [i] = arr [leftIndex + i];
for (int j = 0; j R [j] = arr [middleIndex + 1 + j];
// Slå sammen de midlertidige matriser i arr [leftIndex..rightIndex]
// Innledende indeks for venstre subarray
int i = 0;
// Innledende indeks for høyre undergruppe
int j = 0;
// Innledende indeks for sammenslått underarray
int k = leftIndex;
mens (i {
hvis (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
ellers
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Hvis det er noen gjenværende elementer i L []
// Kopier til arr []
mens (i {
arr [k] = L [i];
i ++;
k ++;
}
// Hvis det er noen gjenværende elementer i R []
// Kopier til arr []
mens (j {
arr [k] = R [j];
j ++;
k ++;
}
}
ugyldig mergeSort (int arr [], int leftIndex, int rightIndex)
{
hvis (leftIndex> = rightIndex)
{
komme tilbake;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
flette (arr, leftIndex, middleIndex, rightIndex);
}
// Funksjon for å skrive ut elementene
// av matrisen
tomrom printArray (int arr [], int størrelse)
{
for (int i = 0; jeg {
cout << arr [i] << "";
}
cout << endl;
}
// Sjåførkode
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int size = sizeof (arr) / sizeof (arr [0]);
cout << "Usortert array:" << endl;
printArray (arr, størrelse);
mergeSort (arr, 0, størrelse - 1);
cout << "Sortert array:" << endl;
printArray (arr, størrelse);
retur 0;
}

Produksjon:

Usortert utvalg:
16 12 15 13 19 17 11 18 
Sortert utvalg:
11 12 13 15 16 17 18 19

JavaScript-implementering av Merge Sort Algorithm

Nedenfor er JavaScript-implementeringen av flersorteringsalgoritmen:

// JavaScript-implementering av
// flette sorteringsalgoritme
// Denne funksjonen slår sammen to underarrayer av arr []
// Venstre subarray: arr [leftIndex..middleIndex]
// Høyre undergruppe: arr [middleIndex + 1..rightIndex]
funksjonssammenslåing (arr, leftIndex, middleIndex, rightIndex) {
la leftSubarraySize = middleIndex - leftIndex + 1;
la rightSubarraySize = rightIndex - middleIndex;
// Lag midlertidige matriser
var L = ny matrise (leftSubarraySize);
var R = ny matrise (rightSubarraySize);
// Kopiere data til midlertidige matriser L [] og R []
for (la i = 0; JegL [i] = arr [leftIndex + i];
}
for (la j = 0; jR [j] = arr [middleIndex + 1 + j];
}
// Slå sammen de midlertidige matriser i arr [leftIndex..rightIndex]
// Innledende indeks for venstre subarray
var i = 0;
// Innledende indeks for høyre undergruppe
var j = 0;
// Innledende indeks for sammenslått underarray
var k = leftIndex;
mens (i {
hvis (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
ellers
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Hvis det er noen gjenværende elementer i L []
// Kopier til arr []
mens (i {
arr [k] = L [i];
i ++;
k ++;
}
// Hvis det er noen gjenværende elementer i R []
// Kopier til arr []
mens (j {
arr [k] = R [j];
j ++;
k ++;
}
}
funksjon mergeSort (arr, leftIndex, rightIndex) {
hvis (leftIndex> = rightIndex) {
komme tilbake
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
flette (arr, leftIndex, middleIndex, rightIndex);
}
// Funksjon for å skrive ut elementene
// av matrisen
funksjon printArray (arr, størrelse) {
for (la i = 0; Jegdocument.write (arr [i] + "");
}
document.write ("
");
}
// Sjåførkode:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var størrelse = arr. lengde;
document.write ("Usortert utvalg:
");
printArray (arr, størrelse);
mergeSort (arr, 0, størrelse - 1);
document.write ("Sortert matrise:
");
printArray (arr, størrelse);

Produksjon:

Usortert utvalg:
16 12 15 13 19 17 11 18
Sortert utvalg:
11 12 13 15 16 17 18 19

I slekt: Dynamisk programmering: Eksempler, vanlige problemer og løsninger

Python Implementation of the Merge Sort Algorithm

Nedenfor er Python-implementeringen av flersorteringsalgoritmen:

# Python implementering av
# flette sorteringsalgoritme
def mergeSort (arr):
hvis len (arr)> 1:
# Finne midtindeksen til matrisen
middleIndex = len (arr) // 2
# Venstre halvdel av matrisen
L = arr [: middleIndex]
# Høyre halvdel av matrisen
R = arr [middleIndex:]
# Sortering av første halvdel av matrisen
mergeSort (L)
# Sortering av andre halvdel av matrisen
mergeSort (R)
# Innledende indeks for venstre subarray
jeg = 0
# Innledende indeks for høyre undergruppe
j = 0
# Innledende indeks for sammenslått undergruppe
k = 0
# Kopier data til midlertidige matriser L [] og R []
mens jeg hvis L [i] arr [k] = L [i]
i = i + 1
ellers:
arr [k] = R [j]
j = j + 1
k = k + 1
# Kontrollerer om det er noen gjenværende elementer
mens jeg arr [k] = L [i]
i = i + 1
k = k + 1
mens j arr [k] = R [j]
j = j + 1
k = k + 1
# Funksjon for å skrive ut elementene
# av matrisen
def printArray (arr, størrelse):
for jeg innen rekkevidde (størrelse):
skriv ut (arr [i], end = "")
skrive ut()
# Førerkode
arr = [16, 12, 15, 13, 19, 17, 11, 18]
størrelse = len (arr)
skriv ut ("Usortert utvalg:")
printArray (arr, størrelse)
mergeSort (arr)
print ("Sorted array:")
printArray (arr, størrelse)

Produksjon:

Usortert utvalg:
16 12 15 13 19 17 11 18
Sortert utvalg:
11 12 13 15 16 17 18 19

Forstå andre sorteringsalgoritmer

Sortering er en av de mest brukte algoritmene i programmering. Du kan sortere elementer på forskjellige programmeringsspråk ved hjelp av forskjellige sorteringsalgoritmer, som hurtig sortering, boblesortering, sammenslåing, sortering osv.

Boblesortering er det beste valget hvis du vil lære om den enkleste sorteringsalgoritmen.

En introduksjon til boblesorteringsalgoritmen

Bubble Sort-algoritmen: en utmerket introduksjon til sorteringsarrayer.

Les Neste

Om forfatteren