Úvod do algoritmu zlučovania a triedenia

Zlúčiť triedenie je algoritmus triedenia založený na technike „rozdeľuj a panuj“. Je to jeden z najefektívnejších algoritmov triedenia.

V tomto článku sa dozviete o práci s algoritmom zlučovania, algoritmom zlučovania a jeho časová a priestorová zložitosť a jej implementácia v rôznych programovacích jazykoch, ako sú C ++, Python a JavaScript.

Ako funguje algoritmus triedenia zlúčenia?

Zlúčenie funguje na princípe rozdelenia a dobývania. Zlúčením zoradenia sa pole opakovane rozdeľuje na dva rovnaké podskupiny, kým sa každé podskupiny nebude skladať z jedného prvku. Nakoniec sa všetky tieto podskupiny zlúčia tak, aby sa výsledné pole zoradilo.

Tento koncept je možné efektívnejšie vysvetliť pomocou príkladu. Zvážte netriedené pole s nasledujúcimi prvkami: {16, 12, 15, 13, 19, 17, 11, 18}.

Tu algoritmus zlúčenia a rozdelenia rozdelí pole na dve polovice, sám sa volá pre dve polovice a potom tieto dve zoradené polovice spojí.

Zlúčiť algoritmus zoradenia

Nižšie je uvedený algoritmus zlučovania:

MergeSort (arr [], leftIndex, rightIndex)
ak leftIndex> = rightIndex
návrat
inak
Nájdite stredný index, ktorý rozdeľuje pole na dve polovice: 
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
Volať mergeSort () pre prvú polovicu: 
Volať mergeSort (arr, leftIndex, middleIndex)
Volať mergeSort () pre druhú polovicu:
Volať mergeSort (arr, middleIndex + 1, rightIndex)
Zlúčte dve polovice zoradené v krokoch 2 a 3:
Zlúčenie hovorov (arr, leftIndex, middleIndex, rightIndex)

Súvisiace: Čo je rekurzia a ako ju používate?

Časová a priestorová zložitosť algoritmu zlučovania

Algoritmus zoradenia zlúčenia je možné vyjadriť vo forme nasledujúceho vzťahu opakovania:

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

Po vyriešení tohto vzťahu opakovania pomocou hlavnej vety alebo metódy stromu opakovania získate riešenie ako O (n logn). Teda časová zložitosť algoritmu zlučovania a triedenia je O (n logn).

Najlepšia časová zložitosť zlúčenia: O (n logn)

Priemerná časová zložitosť druhu zlúčenia: O (n logn)

Najhoršia časová zložitosť zlúčenia: O (n logn)

Súvisiace: Čo je to Big-O notácia?

Zložitosť pomocného priestoru algoritmu triedenia zlúčenia je O (n) ako n pri implementácii triedenia zlúčenia je potrebný pomocný priestor.

C ++ implementácia algoritmu zlúčenia zoradenia

Ďalej uvádzame implementáciu algoritmu zlučovania triedenia v C ++:

// C ++ implementácia
// algoritmus zlúčenia
#include 
pomocou namespace std;
// Táto funkcia zlúči dve podradené polia arr []
// Ľavá podskupina: arr [leftIndex..middleIndex]
// Pravá podskupina: arr [middleIndex + 1..rightIndex]
void merge (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Vytvorte dočasné polia
int L [leftSubarraySize], R [rightSubarraySize];
// Kopírovanie údajov do dočasných polí L [] a R []
pre (int i = 0; i L [i] = arr [leftIndex + i];
pre (int j = 0; j R [j] = arr [middleIndex + 1 + j];
// Zlúčiť dočasné polia späť do arr [leftIndex..rightIndex]
// Počiatočný index ľavého podskupiny
int i = 0;
// Počiatočný index pravej podskupiny
int j = 0;
// Počiatočný index zlúčeného podradeného poľa
int k = leftIndex;
while (i {
if (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
inak
{
aR [k] = R [j];
j ++;
}
k ++;
}
// Ak v L [] zostávajú nejaké prvky
// Kopírovať do príchodu []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Ak v R [] zostávajú nejaké prvky
// Kopírovať do príchodu []
while (j {
aR [k] = R [j];
j ++;
k ++;
}
}
void mergeSort (int arr [], int leftIndex, int rightIndex)
{
if (leftIndex> = rightIndex)
{
návrat;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
zlúčiť (arr, leftIndex, middleIndex, rightIndex);
}
// Funkcia na tlač prvkov
// poľa
void printArray (int arr [], veľkosť int)
{
pre (int i = 0; i {
cout << arr [i] << "";
}
cout << endl;
}
// Kód ovládača
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int size = sizeof (arr) / sizeof (arr [0]);
cout << "Netriedené pole:" << endl;
printArray (veľkosť, veľkosť);
mergeSort (arr, 0, veľkosť - 1);
cout << "Triedené pole:" << endl;
printArray (veľkosť, veľkosť);
návrat 0;
}

Výkon:

Netriedené pole:
16 12 15 13 19 17 11 18 
Zoradené pole:
11 12 13 15 16 17 18 19

Implementácia JavaScriptu algoritmu zlúčenia zoradenia

Nižšie je uvedená implementácia algoritmu zlučovania podľa JavaScriptu:

// Implementácia JavaScriptu
// algoritmus zlúčenia
// Táto funkcia zlúči dve podradené polia arr []
// Ľavá podskupina: arr [leftIndex..middleIndex]
// Pravá podskupina: arr [middleIndex + 1..rightIndex]
zlúčenie funkcií (arr, leftIndex, middleIndex, rightIndex) {
nech leftSubarraySize = middleIndex - leftIndex + 1;
nech rightSubarraySize = rightIndex - middleIndex;
// Vytvorte dočasné polia
var L = nové pole (leftSubarraySize);
var R = nové pole (rightSubarraySize);
// Kopírovanie údajov do dočasných polí L [] a R []
pre (nech i = 0; iL [i] = arr [leftIndex + i];
}
pre (nech j = 0; jR [j] = arr [middleIndex + 1 + j];
}
// Zlúčiť dočasné polia späť do arr [leftIndex..rightIndex]
// Počiatočný index ľavého podskupiny
var i = 0;
// Počiatočný index pravej podskupiny
var j = 0;
// Počiatočný index zlúčeného podradeného poľa
var k = leftIndex;
while (i {
if (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
inak
{
aR [k] = R [j];
j ++;
}
k ++;
}
// Ak v L [] zostávajú nejaké prvky
// Kopírovať do príchodu []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Ak v R [] zostávajú nejaké prvky
// Kopírovať do príchodu []
while (j {
aR [k] = R [j];
j ++;
k ++;
}
}
funkcia mergeSort (arr, leftIndex, rightIndex) {
if (leftIndex> = rightIndex) {
návrat
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
zlúčiť (arr, leftIndex, middleIndex, rightIndex);
}
// Funkcia na tlač prvkov
// poľa
funkcia printArray (veľkosť, veľkosť) {
pre (nech i = 0; idocument.write (arr [i] + "");
}
document.write ("
");
}
// Kód ovládača:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var veľkosť = dorazová dĺžka;
document.write ("Netriedené pole:
");
printArray (veľkosť, veľkosť);
mergeSort (arr, 0, veľkosť - 1);
document.write ("Zoradené pole:
");
printArray (veľkosť, veľkosť);

Výkon:

Netriedené pole:
16 12 15 13 19 17 11 18
Zoradené pole:
11 12 13 15 16 17 18 19

Súvisiace: Dynamické programovanie: Príklady, bežné problémy a riešenia

Implementácia algoritmu zlúčenia zoradenia v jazyku Python

Ďalej je uvedená implementácia algoritmu zlučovania podľa Pythonu:

# Pythonová implementácia
# zlúčiť algoritmus triedenia
def mergeSort (arr):
ak len (arr)> 1:
# Nájdenie stredného indexu poľa
middleIndex = len (arr) // 2
# Ľavá polovica poľa
L = arr [: middleIndex]
# Pravá polovica poľa
R = arr [middleIndex:]
# Triedenie prvej polovice poľa
mergeSort (L)
# Triedenie druhej polovice poľa
mergeSort (R)
# Počiatočný index ľavej podskupiny
i = 0
# Počiatočný index pravej podskupiny
j = 0
# Počiatočný index zlúčeného podradeného poľa
k = 0
# Skopírujte údaje do dočasných polí L [] a R []
while i ak L [i] arr [k] = L [i]
i = i + 1
inak:
arr [k] = R [j]
j = j + 1
k = k + 1
# Kontrola, či tam zostali nejaké prvky
while i arr [k] = L [i]
i = i + 1
k = k + 1
zatiaľ čo j arr [k] = R [j]
j = j + 1
k = k + 1
# Funkcia na tlač prvkov
# poľa
def printArray (veľkosť, veľkosť):
pre i v rozsahu (veľkosť):
print (arr [i], end = "")
print ()
# Kód ovládača
arr = [16, 12, 15, 13, 19, 17, 11, 18]
size = len (arr)
print ("Netriedené pole:")
printArray (veľkosť, veľkosť)
mergeSort (arr)
print ("Zoradené pole:")
printArray (veľkosť, veľkosť)

Výkon:

Netriedené pole:
16 12 15 13 19 17 11 18
Zoradené pole:
11 12 13 15 16 17 18 19

Pochopte ďalšie algoritmy triedenia

Triedenie je jedným z najpoužívanejších algoritmov v programovaní. Prvky môžete triediť v rôznych programovacích jazykoch pomocou rôznych triediacich algoritmov, ako je rýchle triedenie, triedenie podľa bublín, triedenie podľa zlúčenia, triedenie podľa vloženia atď.

Bublinové triedenie je najlepšou voľbou, ak sa chcete dozvedieť viac o najjednoduchšom algoritme triedenia.

Úvod do algoritmu triedenia bublín

Algoritmus Bubble Sort: vynikajúci úvod do triedenia polí.

Prečítajte si Ďalej

O autorovi