Uvod v algoritem sortiranja spajanja

Merge sort je algoritem za razvrščanje, ki temelji na tehniki "deli in osvoji". To je eden najučinkovitejših algoritmov za razvrščanje.

V tem članku boste izvedeli o delovanju algoritma za razvrščanje merge, algoritmu razvrščanja po združitvah in njegovem časovno in prostorsko zapletenost ter njeno izvajanje v različnih programskih jezikih, kot so C ++, Python in JavaScript.

Kako deluje algoritem razvrščanja merge?

Razvrščanje po združitvi deluje po principu deli in vladaj. Razvrščanje združevanja večkrat razbije matriko na dva enaka podniz, dokler vsaka podmreža ni sestavljena iz enega samega elementa. Na koncu so vsi ti podnizi združeni tako, da je nastalo polje razvrščeno.

Ta koncept lahko učinkoviteje razložimo s pomočjo primera. Razmislite o nesortirani matriki z naslednjimi elementi: {16, 12, 15, 13, 19, 17, 11, 18}.

Tu algoritem za razvrščanje merge razdeli matriko na dve polovici, se pokliče za dve polovici in nato združi dve razvrščeni polovici.

Spoji algoritem razvrščanja

Spodaj je algoritem razvrščanja:

MergeSort (arr [], leftIndex, rightIndex)
če leftIndex> = rightIndex
vrnitev
drugače
Poiščite srednji indeks, ki matriko deli na dve polovici: 
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
Za prvo polovico pokličite mergeSort (): 
Pokliči mergeSort (arr, leftIndex, middleIndex)
Za drugo polovico pokličite mergeSort ():
Pokliči mergeSort (arr, middleIndex + 1, rightIndex)
Združite dve polovici, razvrščeni v korakih 2 in 3:
Spajanje klicev (arr, leftIndex, middleIndex, rightIndex)

Sorodno: Kaj je rekurzija in kako jo uporabljate?

Časovna in prostorska zapletenost algoritma sortiranja spajanja

Algoritem razvrščanja merge je lahko izražen v obliki naslednje relacije ponovitve:

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

Po rešitvi tega relativnega razmerja z uporabo glavnega izreka ali metode drevesa ponovitve boste dobili rešitev kot O (n logn). Tako je časovna zapletenost algoritma za združevanje razvrščena O (n prijava).

Najboljša časovna zapletenost vrste spajanja: O (n prijava)

Povprečna časovna zapletenost vrste spajanja: O (n prijava)

Najslabša časovna zapletenost vrste spajanja: O (n prijava)

Sorodno: Kaj je zapis Big-O?

Kompleksnost pomožnega prostora algoritma za združevanje je O (n) kot n pri izvedbi sortiranja spajanja je potreben pomožni prostor.

C ++ Izvajanje algoritma za sortiranje spajanja

Spodaj je izvedba algoritma za razvrščanje merge na C ++:

// C ++ izvedba
// spajanje algoritmov za razvrščanje
#include 
uporaba imenskega prostora std;
// Ta funkcija združi dve podredji arr []
// Leva podniz: arr [leftIndex..middleIndex]
// Desna podniz: arr [middleIndex + 1..rightIndex]
spajanje void (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Ustvari začasna polja
int L [leftSubarraySize], R [rightSubarraySize];
// kopiranje podatkov v začasna polja L [] in R []
za (int i = 0; i L [i] = arr [leftIndex + i];
za (int j = 0; j R [j] = arr [middleIndex + 1 + j];
// Združi začasna polja nazaj v arr [leftIndex..rightIndex]
// Začetni indeks leve podmreže
int i = 0;
// Začetni indeks desne podmreže
int j = 0;
// Začetni indeks združene podmreže
int k = leftIndex;
medtem ko (i {
če (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
drugače
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Če je v L nekaj preostalih elementov []
// Kopiraj v arr []
medtem ko (i {
arr [k] = L [i];
i ++;
k ++;
}
// Če je v R nekaj preostalih elementov []
// Kopiraj v arr []
medtem ko (j {
arr [k] = R [j];
j ++;
k ++;
}
}
void mergeSort (int arr [], int leftIndex, int rightIndex)
{
če (leftIndex> = rightIndex)
{
vrnitev;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
spajanje (arr, leftIndex, middleIndex, rightIndex);
}
// Funkcija tiskanja elementov
// polja
void printArray (int arr [], int velikost)
{
za (int i = 0; i {
cout << arr [i] << "";
}
cout << endl;
}
// Koda gonilnika
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int size = sizeof (arr) / sizeof (arr [0]);
cout << "Nerazvrščena matrika:" << endl;
printArray (dol, velikost);
mergeSort (arr, 0, velikost - 1);
cout << "Razvrščeno polje:" << endl;
printArray (dol, velikost);
vrnitev 0;
}

Izhod:

Nerazvrščena matrika:
16 12 15 13 19 17 11 18 
Razvrščeno polje:
11 12 13 15 16 17 18 19

Izvajanje JavaScript algoritma za sortiranje spajanja

Spodaj je izvedba JavaScript algoritma za združevanje:

// JavaScript izvedba
// spajanje algoritmov za razvrščanje
// Ta funkcija združi dve podredji arr []
// Leva podniz: arr [leftIndex..middleIndex]
// Desna podniz: arr [middleIndex + 1..rightIndex]
spajanje funkcij (arr, leftIndex, middleIndex, rightIndex) {
naj leftSubarraySize = middleIndex - leftIndex + 1;
naj rightSubarraySize = rightIndex - middleIndex;
// Ustvari začasna polja
var L = novo polje (leftSubarraySize);
var R = novo polje (rightSubarraySize);
// kopiranje podatkov v začasna polja L [] in R []
za (naj je i = 0; jazL [i] = arr [leftIndex + i];
}
za (naj bo j = 0; jR [j] = arr [middleIndex + 1 + j];
}
// Združi začasna polja nazaj v arr [leftIndex..rightIndex]
// Začetni indeks leve podmreže
var i = 0;
// Začetni indeks desne podmreže
var j = 0;
// Začetni indeks združene podmreže
var k = leftIndex;
medtem ko (i {
če (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
drugače
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Če je v L nekaj preostalih elementov []
// Kopiraj v arr []
medtem ko (i {
arr [k] = L [i];
i ++;
k ++;
}
// Če je v R nekaj preostalih elementov []
// Kopiraj v arr []
medtem ko (j {
arr [k] = R [j];
j ++;
k ++;
}
}
funkcija mergeSort (arr, leftIndex, rightIndex) {
če (leftIndex> = rightIndex) {
vrnitev
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
spajanje (arr, leftIndex, middleIndex, rightIndex);
}
// Funkcija tiskanja elementov
// polja
funkcija printArray (arr, velikost) {
za (naj je i = 0; jazdocument.write (arr [i] + "");
}
document.write ("
");
}
// Koda gonilnika:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var size = dolžina arr;
document.write ("Nesortirana matrika:
");
printArray (dol, velikost);
mergeSort (arr, 0, velikost - 1);
document.write ("Razvrščeno polje:
");
printArray (dol, velikost);

Izhod:

Nerazvrščena matrika:
16 12 15 13 19 17 11 18
Razvrščeno polje:
11 12 13 15 16 17 18 19

Sorodno: Dinamično programiranje: primeri, pogosti problemi in rešitve

Python Implementacija algoritma sortiranja spajanja

Spodaj je izvedba Pythona algoritma za združevanje:

# Python izvedba
# spajanje algoritem razvrščanja
def mergeSort (arr):
če je len (arr)> 1:
# Iskanje srednjega indeksa polja
middleIndex = len (arr) // 2
# Leva polovica polja
L = arr [: middleIndex]
# Desna polovica polja
R = arr [middleIndex:]
# Razvrščanje prve polovice polja
mergeSort (L)
# Razvrščanje druge polovice polja
mergeSort (R)
# Začetni indeks leve podmreže
i = 0
# Začetni indeks desne podniz
j = 0
# Začetni indeks združene podmreže
k = 0
# Kopiranje podatkov v začasna polja L [] in R []
medtem ko je i če je L [i] arr [k] = L [i]
i = i + 1
sicer:
arr [k] = R [j]
j = j + 1
k = k + 1
# Preverjanje, ali je nekaj preostalih elementov
medtem ko i arr [k] = L [i]
i = i + 1
k = k + 1
medtem ko j arr [k] = R [j]
j = j + 1
k = k + 1
# Funkcija za tiskanje elementov
# polja
def printArray (arr, velikost):
za i v območju (velikost):
natisni (arr [i], end = "")
natisni ()
# Koda gonilnika
arr = [16, 12, 15, 13, 19, 17, 11, 18]
velikost = len (arr)
print ("Nesortirana matrika:")
printArray (dol, velikost)
mergeSort (arr)
print ("Razvrščeno polje:")
printArray (dol, velikost)

Izhod:

Nerazvrščena matrika:
16 12 15 13 19 17 11 18
Razvrščeno polje:
11 12 13 15 16 17 18 19

Razumevanje drugih algoritmov za razvrščanje

Razvrščanje je eden najpogosteje uporabljenih algoritmov pri programiranju. Elemente lahko razvrščate v različnih programskih jezikih z različnimi algoritmi za razvrščanje, kot so hitro razvrščanje, razvrščanje po mehurčkih, združevanje, razvrščanje med vstavljanjem itd.

Razvrstitev po mehurčkih je najboljša izbira, če želite izvedeti o najpreprostejšem algoritmu za razvrščanje.

Uvod v algoritem razvrščanja mehurčkov

Algoritem razvrščanja po mehurčkih: odličen uvod v razvrščanje nizov.

Preberite Naprej

O avtorju