Úvod do algoritmu sloučení řazení

Merge sort je třídicí algoritmus založený na technice „rozděl a panuj“. Je to jeden z nejúčinnějších třídicích algoritmů.

V tomto článku se dozvíte o fungování algoritmu sloučení, algoritmu sloučení a jeho časová a prostorová složitost a její implementace v různých programovacích jazycích, jako jsou C ++, Python a JavaScript.

Jak funguje algoritmus sloučení řazení?

Sloučení typu sloučení funguje na principu rozděl a panuj. Sloučit řazení opakovaně rozdělí pole do dvou stejných dílčích polí, dokud se každé dílčí pole nebude skládat z jednoho prvku. Nakonec jsou všechny tyto podskupiny sloučeny tak, že je výsledné pole tříděno.

Tento koncept lze efektivněji vysvětlit pomocí příkladu. Zvažte netříděné pole s následujícími prvky: {16, 12, 15, 13, 19, 17, 11, 18}.

Zde algoritmus sloučení řazení rozděluje pole na dvě poloviny, volá se pro dvě poloviny a poté spojí dvě tříděné poloviny.

Sloučit algoritmus řazení

Níže je uveden algoritmus sloučení:

MergeSort (arr [], leftIndex, rightIndex)





instagram viewer


pokud leftIndex> = rightIndex
vrátit se
jiný
Najděte střední index, který rozděluje pole na dvě poloviny: 
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
Volejte mergeSort () pro první polovinu: 
Volejte mergeSort (arr, leftIndex, middleIndex)
Volejte mergeSort () pro druhou polovinu:
Volejte mergeSort (arr, middleIndex + 1, rightIndex)
Sloučte dvě poloviny seřazené v kroku 2 a 3:
Sloučení hovorů (arr, leftIndex, middleIndex, rightIndex)

Příbuzný: Co je rekurze a jak ji používáte?

Časová a prostorová složitost algoritmu sloučení řazení

Algoritmus sloučení řazení lze vyjádřit ve formě následujícího relace opakování:

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

Po vyřešení této relace opakování pomocí hlavní věty nebo metody stromu opakování získáte řešení jako O (n logn). Časová složitost algoritmu sloučení je tedy časová O (n logn).

Nejlepší časová složitost sloučení: O (n logn)

Průměrná časová složitost sloučení: O (n logn)

Nejhorší časová složitost sloučení: O (n logn)

Příbuzný: Co je Big-O notace?

Složitost pomocného prostoru algoritmu sloučení je Na) tak jako n v implementaci řazení sloučení je vyžadován pomocný prostor.

C ++ implementace algoritmu sloučení řazení

Níže je implementace C ++ algoritmu sloučení sloučení v C ++:

// C ++ implementace
// sloučit třídicí algoritmus
#zahrnout 
pomocí jmenného prostoru std;
// Tato funkce sloučí dvě dílčí pole arr []
// Levá podskupina: arr [leftIndex..middleIndex]
// Pravá podoblast: arr [middleIndex + 1..rightIndex]
sloučení void (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Vytváření dočasných polí
int L [leftSubarraySize], R [rightSubarraySize];
// Kopírování dat do dočasných polí L [] a R []
pro (int i = 0; i L [i] = arr [leftIndex + i];
pro (int j = 0; j R [j] = arr [middleIndex + 1 + j];
// Sloučí dočasná pole zpět do arr [leftIndex..rightIndex]
// Počáteční index levé podskupiny
int i = 0;
// Počáteční index pravého dílčího pole
int j = 0;
// Počáteční index sloučeného dílčího pole
int k = leftIndex;
while (i {
if (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
jiný
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Pokud jsou v L [] nějaké zbývající prvky
// Kopírovat do příchodu []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Pokud jsou v R [] nějaké zbývající prvky
// Kopírovat do příchodu []
while (j {
arr [k] = R [j];
j ++;
k ++;
}
}
void mergeSort (int arr [], int leftIndex, int rightIndex)
{
if (leftIndex> = rightIndex)
{
vrátit se;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
sloučit (arr, leftIndex, middleIndex, rightIndex);
}
// Funkce pro tisk prvků
// pole
void printArray (int arr [], velikost int)
{
pro (int i = 0; i {
cout << arr [i] << "";
}
cout << endl;
}
// Kód ovladače
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int size = sizeof (arr) / sizeof (arr [0]);
cout << "Netříděné pole:" << endl;
printArray (arr, velikost);
mergeSort (arr, 0, velikost - 1);
cout << "Řaděné pole:" << endl;
printArray (arr, velikost);
návrat 0;
}

Výstup:

Netříděné pole:
16 12 15 13 19 17 11 18 
Seřazené pole:
11 12 13 15 16 17 18 19

Implementace JavaScriptu algoritmu sloučení řazení

Níže je implementace JavaScriptu algoritmu sloučení řazení:

// Implementace JavaScriptu
// sloučit třídicí algoritmus
// Tato funkce sloučí dvě dílčí pole arr []
// Levá podskupina: arr [leftIndex..middleIndex]
// Pravá podoblast: arr [middleIndex + 1..rightIndex]
sloučení funkcí (arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
// Vytváření dočasných polí
var L = nové pole (leftSubarraySize);
var R = nové pole (rightSubarraySize);
// Kopírování dat do dočasných polí L [] a R []
pro (nechť i = 0; iL [i] = arr [leftIndex + i];
}
pro (nechť j = 0; jR [j] = arr [middleIndex + 1 + j];
}
// Sloučí dočasná pole zpět do arr [leftIndex..rightIndex]
// Počáteční index levé podskupiny
var i = 0;
// Počáteční index pravého dílčího pole
var j = 0;
// Počáteční index sloučeného dílčího pole
var k = leftIndex;
while (i {
if (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
jiný
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Pokud jsou v L [] nějaké zbývající prvky
// Kopírovat do příchodu []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Pokud jsou v R [] nějaké zbývající prvky
// Kopírovat do příchodu []
while (j {
arr [k] = R [j];
j ++;
k ++;
}
}
funkce mergeSort (arr, leftIndex, rightIndex) {
if (leftIndex> = rightIndex) {
vrátit se
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
sloučit (arr, leftIndex, middleIndex, rightIndex);
}
// Funkce pro tisk prvků
// pole
funkce printArray (arr, velikost) {
pro (nechť i = 0; idocument.write (arr [i] + "");
}
document.write ("
");
}
// Kód ovladače:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var velikost = dorazová délka;
document.write ("Nezařazené pole:
");
printArray (arr, velikost);
mergeSort (arr, 0, velikost - 1);
document.write ("Řazené pole:
");
printArray (arr, velikost);

Výstup:

Netříděné pole:
16 12 15 13 19 17 11 18
Seřazené pole:
11 12 13 15 16 17 18 19

Příbuzný: Dynamické programování: příklady, běžné problémy a řešení

Pythonská implementace algoritmu sloučení řazení

Níže je implementace algoritmu slučovacího řazení v Pythonu:

# Pythonová implementace
# sloučit algoritmus třídění
def mergeSort (arr):
pokud len (arr)> 1:
# Nalezení středního indexu pole
middleIndex = len (arr) // 2
# Levá polovina pole
L = arr [: middleIndex]
# Pravá polovina pole
R = arr [middleIndex:]
# Třídění první poloviny pole
mergeSort (L)
# Třídění druhé poloviny pole
mergeSort (R)
# Počáteční index levé podskupiny
i = 0
# Počáteční index pravého dílčího pole
j = 0
# Počáteční index sloučeného dílčího pole
k = 0
# Zkopírujte data do dočasných polí L [] a R []
while i pokud L [i] arr [k] = L [i]
i = i + 1
jiný:
arr [k] = R [j]
j = j + 1
k = k + 1
# Kontrola, zda tam zůstaly nějaké zbývající prvky
while i arr [k] = L [i]
i = i + 1
k = k + 1
while j arr [k] = R [j]
j = j + 1
k = k + 1
# Funkce pro tisk prvků
# pole
def printArray (arr, velikost):
pro i v rozsahu (velikost):
print (arr [i], end = "")
tisk()
# Kód ovladače
arr = [16, 12, 15, 13, 19, 17, 11, 18]
size = len (arr)
print ("Netříděné pole:")
printArray (arr, velikost)
mergeSort (arr)
print ("Řaděné pole:")
printArray (arr, velikost)

Výstup:

Netříděné pole:
16 12 15 13 19 17 11 18
Seřazené pole:
11 12 13 15 16 17 18 19

Pochopte další algoritmy řazení

Třídění je jedním z nejpoužívanějších algoritmů v programování. Prvky můžete třídit v různých programovacích jazycích pomocí různých třídicích algoritmů, jako je rychlé řazení, třídění bublin, sloučení, vložení atd.

Bubble sort je nejlepší volbou, pokud se chcete dozvědět o nejjednodušším algoritmu třídění.

Úvod do algoritmu třídění bublin

Algoritmus Bubble Sort: vynikající úvod do třídicích polí.

Přečtěte si další

O autorovi