Spajanje sortiranjem algoritam je sortiranja zasnovan na tehnici "podijeli i osvoji". To je jedan od najučinkovitijih algoritama za sortiranje.

U ovom ćete članku naučiti o radu algoritma za sortiranje spajanja, algoritmu sortiranja za spajanje, njegovom složenost vremena i prostora, te njegova primjena u raznim programskim jezicima poput C ++, Python i JavaScript.

Kako funkcionira algoritam sortiranja stapanja?

Sortiranje spajanja djeluje na principu podijeli i osvoji. Sortiranje spajanja više puta raščlanjuje niz na dva jednaka podniza dok se svaki podniz ne sastoji od jednog elementa. Konačno, svi se ti nizovi spoje tako da se rezultirajući niz sortira.

Ovaj se koncept može učinkovitije objasniti uz pomoć primjera. Razmotrite nesortirani niz sa sljedećim elementima: {16, 12, 15, 13, 19, 17, 11, 18}.

Ovdje algoritam sortiranja spajanja dijeli niz na dvije polovice, poziva se na dvije polovice, a zatim spaja dvije sortirane polovice.

Spoji algoritam sortiranja

Ispod je algoritam sortiranja spajanja:

instagram viewer 
MergeSort (arr [], leftIndex, rightIndex)
ako leftIndex> = rightIndex
povratak
drugo
Pronađite srednji indeks koji dijeli niz na dvije polovice: 
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
Pozovite mergeSort () za prvo poluvrijeme: 
Pozovite mergeSort (arr, leftIndex, middleIndex)
Nazovite mergeSort () za drugo poluvrijeme:
Pozovite mergeSort (arr, middleIndex + 1, rightIndex)
Spojite dvije polovice sortirane u koraku 2 i 3:
Spajanje poziva (arr, leftIndex, middleIndex, rightIndex)

Povezano: Što je rekurzija i kako je koristite?

Složenost vremena i prostora algoritma sortiranja stapanja

Algoritam sortiranja spajanja može se izraziti u obliku sljedeće relacije ponavljanja:

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

Nakon rješavanja ove relacije ponavljanja pomoću master teorema ili metode stabla ponavljanja, dobit ćete rješenje kao O (n logn). Dakle, vremenska složenost algoritma za spajanje je O (n prijava).

Najbolja vremenska složenost vrste spajanja: O (n prijava)

Prosječna vremenska složenost vrste spajanja: O (n prijava)

Najgora vremenska složenost vrste spajanja: O (n prijava)

Povezano: Što je oznaka Big-O?

Kompleksnost pomoćnog prostora algoritma za sortiranje spajanja je Na) kao n potreban je pomoćni prostor u provedbi sortiranja spajanja.

C ++ Implementacija algoritma sortiranja stapanja

Ispod je implementacija C ++ algoritma za spajanje: 

// C ++ implementacija
// spajanje algoritma sortiranja
#include 
pomoću prostora imena std;
// Ova funkcija spaja dva podsklopa arr []
// Lijevi podred: arr [leftIndex..middleIndex]
// Desni podniz: arr [middleIndex + 1..rightIndex]
spajanje praznina (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Stvaranje privremenih nizova
int L [leftSubarraySize], R [rightSubarraySize];
// Kopiranje podataka u privremene nizove L [] i R []
za (int i = 0; i L [i] = arr [leftIndex + i];
za (int j = 0; j R [j] = arr [srednji indeks + 1 + j];
// Spajanje privremenih nizova natrag u arr [leftIndex..rightIndex]
// Početni indeks lijevog podreza
int i = 0;
// Početni indeks desnog podreza
int j = 0;
// Početni indeks spojenog niza
int k = leftIndex;
dok (i {
ako (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
drugo
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Ako u L ima nekih preostalih elemenata []
// Kopiraj u arr []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Ako postoje neki preostali elementi u R []
// Kopiraj u arr []
while (j {
arr [k] = R [j];
j ++;
k ++;
}
}
void mergeSort (int arr [], int leftIndex, int rightIndex)
{
if (leftIndex> = rightIndex)
{
povratak;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
spajanje (arr, leftIndex, middleIndex, rightIndex);
}
// Funkcija ispisa elemenata
// niza
void printArray (int arr [], int veličina)
{
za (int i = 0; i {
cout << arr [i] << "";
}
cout << endl;
}
// Šifra vozača
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int veličina = veličina (arr) / veličina (arr [0]);
cout << "Nesortirani niz:" << endl;
printArray (arr, veličina);
mergeSort (arr, 0, veličina - 1);
cout << "Sortirani niz:" << endl;
printArray (arr, veličina);
return 0;
}

Izlaz: 

Nerazvrstani niz:
16 12 15 13 19 17 11 18 
Sortirani niz:
11 12 13 15 16 17 18 19

Implementacija JavaScript algoritma sortiranja stapanja

Ispod je implementacija JavaScript-a algoritma za spajanje: 

// JavaScript implementacija
// spajanje algoritma sortiranja
// Ova funkcija spaja dva podsklopa arr []
// Lijevi podred: arr [leftIndex..middleIndex]
// Desni podniz: arr [middleIndex + 1..rightIndex]
spajanje funkcija (arr, leftIndex, middleIndex, rightIndex) {
neka leftSubarraySize = middleIndex - leftIndex + 1;
neka rightSubarraySize = rightIndex - middleIndex;
// Stvaranje privremenih nizova
var L = novi niz (leftSubarraySize);
var R = novi niz (rightSubarraySize);
// Kopiranje podataka u privremene nizove L [] i R []
za (neka je i = 0; jaL [i] = arr [leftIndex + i];
}
za (neka j = 0; jR [j] = arr [srednji indeks + 1 + j];
}
// Spajanje privremenih nizova natrag u arr [leftIndex..rightIndex]
// Početni indeks lijevog podreza
var i = 0;
// Početni indeks desnog podreza
var j = 0;
// Početni indeks spojenog niza
var k = leftIndex;
dok (i {
ako (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
drugo
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Ako u L ima nekih preostalih elemenata []
// Kopiraj u arr []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Ako postoje neki preostali elementi u R []
// Kopiraj u arr []
while (j {
arr [k] = R [j];
j ++;
k ++;
}
}
funkcija mergeSort (arr, leftIndex, rightIndex) {
if (leftIndex> = rightIndex) {
povratak
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
spajanje (arr, leftIndex, middleIndex, rightIndex);
}
// Funkcija ispisa elemenata
// niza
funkcija printArray (arr, veličina) {
za (neka je i = 0; jadocument.write (arr [i] + "");
}
document.write ("
");
}
// šifra vozača:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var veličina = dužina arr.length;
document.write ("Nesortirani niz:
");
printArray (arr, veličina);
mergeSort (arr, 0, veličina - 1);
document.write ("Sortirani niz:
");
printArray (arr, veličina);

Izlaz: 

Nerazvrstani niz:
16 12 15 13 19 17 11 18
Sortirani niz:
11 12 13 15 16 17 18 19

Povezano: Dinamičko programiranje: primjeri, uobičajeni problemi i rješenja

Python implementacija algoritma sortiranja stapanja

Ispod je implementacija Pythona algoritma za spajanje: 

# Python implementacija
# spajanje algoritma sortiranja
def mergeSort (arr):
ako je len (arr)> 1:
# Pronalaženje srednjeg indeksa niza
middleIndex = len (arr) // 2
# Lijeva polovica niza
L = arr [: middleIndex]
# Desna polovica niza
R = arr [middleIndex:]
# Sortiranje prve polovice niza
spajanje (L)
# Sortiranje druge polovice niza
mergeSort (R)
# Inicijalni indeks lijevog podreza
i = 0
# Inicijalni indeks desnog podniza
j = 0
# Inicijalni indeks spojenog niza
k = 0
# Kopiranje podataka u privremene nizove L [] i R []
dok je i ako je L [i] arr [k] = L [i]
i = i + 1
drugo:
arr [k] = R [j]
j = j + 1
k = k + 1
# Provjera ima li preostalih elemenata
dok je i arr [k] = L [i]
i = i + 1
k = k + 1
dok je j arr [k] = R [j]
j = j + 1
k = k + 1
# Funkcija za ispis elemenata
# polja
def printArray (arr, veličina):
za i u opsegu (veličina):
ispis (arr [i], end = "")
ispis ()
# Šifra vozača
arr = [16, 12, 15, 13, 19, 17, 11, 18]
veličina = len (arr)
print ("Nesortirani niz:")
printArray (arr, veličina)
mergeSort (arr)
print ("Sortirani niz:")
printArray (arr, veličina)

Izlaz: 

Nerazvrstani niz:
16 12 15 13 19 17 11 18
Sortirani niz:
11 12 13 15 16 17 18 19

Razumijevanje ostalih algoritama sortiranja

Sortiranje je jedan od najčešće korištenih algoritama u programiranju. Možete sortirati elemente u različitim programskim jezicima pomoću različitih algoritama za sortiranje poput brzog sortiranja, mjehurića sortiranja, sortiranja spajanjem, sortiranja umetanjem itd.

Razvrstavanje mjehurića najbolji je izbor ako želite naučiti najjednostavniji algoritam sortiranja.

E-mail
Uvod u algoritam sortiranja mjehurića

Algoritam sortiranja mjehurića: izvrstan uvod u sortiranje nizova.

Pročitajte Dalje

Povezane teme
  • Programiranje
  • JavaScript
  • Piton
  • Vodiči za kodiranje
O autoru
Yuvraj Chandra (Objavljeno 27 članaka)

Yuvraj je studentica preddiplomskog studija računarstva na Sveučilištu u Delhiju u Indiji. Zaljubljen je u Full Stack web razvoj. Kad ne piše, istražuje dubinu različitih tehnologija.

Više od Yuvraja Chandre

Pretplatite se na naše obavijesti

Pridružite se našem biltenu za tehničke savjete, recenzije, besplatne e-knjige i ekskluzivne ponude!

Još jedan korak…!

Potvrdite svoju e-adresu u e-pošti koju smo vam upravo poslali.

.