Ühenda sortimine on "jaga ja võida" tehnikal põhinev sortimisalgoritm. See on üks tõhusamaid sorteerimisalgoritme.

Selles artiklis saate teada ühendamise sordi algoritmi, ühendamise sordi algoritmi, selle aja ja ruumi keerukus ning selle rakendamine erinevates programmeerimiskeeltes, nagu C ++, Python ja JavaScripti.

Kuidas ühendamise algoritm töötab?

Ühenda sortimine töötab jagamise ja vallutamise põhimõttel. Ühendamise sortimine jagab massiivi korduvalt kaheks võrdseks alamkihiks, kuni iga alamkord koosneb ühest elemendist. Lõpuks ühendatakse kõik need alamrajad nii, et tulemuseks olev massiiv sorteeritakse.

Seda mõistet saab näite abil tõhusamalt seletada. Vaatleme sorteerimata massiivi, millel on järgmised elemendid: {16, 12, 15, 13, 19, 17, 11, 18}.

Siin jagab ühendamise sortimise algoritm massiivi kaheks pooleks, kutsub ennast kaheks pooleks ja liidab seejärel kaks sorteeritud poolt.

Ühenda sortimisalgoritm

Allpool on ühendatud sordi algoritm: 

MergeSort (arr [], leftIndex, rightIndex)

kui vasakIndex> = rightIndex
tagasi
muud
Leidke keskmine indeks, mis jagab massiivi kaheks pooleks: 
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
Esimese poole kõne mergeSort (): 
Kõne ühendamineSorteeri (arr, leftIndex, middleIndex)
Teise poole kõne mergeSort ():
Kõne ühendamineSorteeri (arr, middleIndex + 1, rightIndex)
Ühendage 2. ja 3. etapis sorteeritud pooled:
Kõne ühendamine (arr, leftIndex, middleIndex, rightIndex)

Seotud: Mis on rekursioon ja kuidas seda kasutada?

Ühendamise sortimise algoritmi aja ja ruumi keerukus

Sorteerimise algoritmi saab väljendada järgmise kordussuhte kujul:

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

Pärast selle kordumissuhte lahendamist, kasutades peamist teoreemi või kordumispuu meetodit, saate lahendi kujul O (n logn). Seega on ühendamise sortimise algoritmi ajaline keerukus O (n logn).

Parim juhtumite keerukuse aeg: O (n logn)

Ühendamise sordi keskmine juhtumi aja keerukus: O (n logn)

Ühinemise sordi halvim juhtumite keerukus: O (n logn)

Seotud: Mis on Big-O tähistamine?

Abiruumi keerukus liidetud sortimisalgoritm on Peal) as n ühendamissordi rakendamisel on vaja lisaruumi.

C ++ Ühendamise sortimise algoritmi rakendamine

Allpool on ühendatud Sorteerimise algoritmi C ++ rakendamine: 

// C ++ rakendamine
// liita sortimisalgoritm
# kaasata 
nimeruumi kasutamine std;
// See funktsioon liidab arr-i kaks alamkaarti
// Vasak alamkaart: arr [leftIndex..middleIndex]
// Parem alamkaart: arr [middleIndex + 1..rightIndex]
void merge (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Loo ajutised massiivid
int L [leftSubarraySize], R [rightSubarraySize];
// Andmete kopeerimine ajutistesse massiividesse L [] ja R []
for (int i = 0; i L [i] = arr [vasakIndex + i];
for (int j = 0; j R [j] = arr [keskindeks + 1 + j];
// Ühendage ajutised massiivid tagasi arr [leftIndex..rightIndex]
// Vasaku alamkihi algindeks
int i = 0;
// Parempoolse alamkaardi algindeks
int j = 0;
// Ühendatud alamraja algindeks
int k = vasakIndex;
while (i {
kui (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
muud
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Kui L-s on veel mõned elemendid
// Kopeeri arr []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Kui R-s on veel mõned elemendid
// Kopeeri arr []
samas (j {
arr [k] = R [j];
j ++;
k ++;
}
}
void mergeSort (int arr [], int leftIndex, int rightIndex)
{
if (leftIndex> = rightIndex)
{
tagasi;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
ühendama (arr, leftIndex, middleIndex, rightIndex);
}
// Funktsioon elementide printimiseks
massiivi //
void printArray (int arr [], int suurus)
{
for (int i = 0; i {
cout << arr [i] << "";
}
cout << endl;
}
// Draiveri kood
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int suurus = suurus (arr) / suurusof (arr [0]);
cout << "Sorteerimata massiiv:" << endl;
printArray (arr, suurus);
mergeSort (arr, 0, suurus - 1);
cout << "Sorteeritud massiiv:" << endl;
printArray (arr, suurus);
tagastama 0;
}

Väljund: 

Sorteerimata massiiv:
16 12 15 13 19 17 11 18 
Sorteeritud massiiv:
11 12 13 15 16 17 18 19

JavaSordi algoritmi JavaScripti rakendamine

Allpool on ühendatud sordi algoritmi JavaScripti rakendamine: 

// JavaScripti rakendamine
// liita sortimisalgoritm
// See funktsioon liidab arr-i kaks alamkaarti
// Vasak alamkaart: arr [leftIndex..middleIndex]
// Parem alamkaart: arr [middleIndex + 1..rightIndex]
funktsiooni ühendamine (arr, leftIndex, middleIndex, rightIndex) {
olgu vasakSubarraySize = middleIndex - leftIndex + 1;
olgu rightSubarraySize = rightIndex - middleIndex;
// Loo ajutised massiivid
var L = uus massiiv (leftSubarraySize);
var R = uus massiiv (rightSubarraySize);
// Andmete kopeerimine ajutistesse massiividesse L [] ja R []
for (olgu i = 0; iL [i] = arr [vasakIndex + i];
}
for (olgu j = 0; jR [j] = arr [keskindeks + 1 + j];
}
// Ühendage ajutised massiivid tagasi arr [leftIndex..rightIndex]
// Vasaku alamkihi algindeks
var i = 0;
// Parempoolse alamkaardi algindeks
var j = 0;
// Ühendatud alamraja algindeks
var k = leftIndex;
while (i {
kui (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
muud
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Kui L-s on veel mõned elemendid
// Kopeeri arr []
while (i {
arr [k] = L [i];
i ++;
k ++;
}
// Kui R-s on veel mõned elemendid
// Kopeeri arr []
samas (j {
arr [k] = R [j];
j ++;
k ++;
}
}
function mergeSort (arr, leftIndex, rightIndex) {
if (leftIndex> = rightIndex) {
tagasi
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
ühendama (arr, leftIndex, middleIndex, rightIndex);
}
// Funktsioon elementide printimiseks
massiivi //
funktsioon printArray (arr, suurus) {
for (olgu i = 0; idocument.write (arr [i] + "");
}
document.write ("
");
}
// Juhi kood:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var size = arr.length;
document.write ("sortimata massiiv:
");
printArray (arr, suurus);
mergeSort (arr, 0, suurus - 1);
document.write ("Sorteeritud massiiv:
");
printArray (arr, suurus);

Väljund: 

Sorteerimata massiiv:
16 12 15 13 19 17 11 18
Sorteeritud massiiv:
11 12 13 15 16 17 18 19

Seotud: Dünaamiline programmeerimine: näited, levinumad probleemid ja lahendused

Ühendamise sortimise algoritmi Pythoni rakendamine

Allpool on ühendatud sordi algoritmi Pythoni rakendus: 

# Pythoni rakendamine
# liita sortimisalgoritm
def mergeSort (arr):
kui len (arr)> 1:
# Massiivi keskmise indeksi leidmine
middleIndex = len (arr) // 2
# Massiivi vasak pool
L = arr [: middleIndex]
# Parem pool massiivist
R = arr [keskindeks:]
# Massiivi esimese poole sortimine
mergeSort (L)
# Massiivi teise poole sortimine
mergeSort (R)
# Vasaku alamkaardi algindeks
i = 0
# Parempoolse alamkaardi algindeks
j = 0
# Ühendatud alamindeksi esialgne indeks
k = 0
# Kopeeri andmed tempermassiividesse L [] ja R []
samas kui i kui L [i] arr [k] = L [i]
i = i + 1
muu:
arr [k] = R [j]
j = j + 1
k = k + 1
# Kontrollige, kas on veel mõnda elementi
samal ajal kui ma arr [k] = L [i]
i = i + 1
k = k + 1
samas kui j arr [k] = R [j]
j = j + 1
k = k + 1
# Funktsioon elementide printimiseks
Massiivi #
def printArray (arr, suurus):
i jaoks vahemikus (suurus):
print (arr [i], end = "")
print ()
# Juhi kood
arr = [16, 12, 15, 13, 19, 17, 11, 18]
suurus = len (arr)
print ("sortimata massiiv:")
printArray (arr, suurus)
mergeSort (arr)
print ("Sorteeritud massiiv:")
printArray (arr, suurus)

Väljund: 

Sorteerimata massiiv:
16 12 15 13 19 17 11 18
Sorteeritud massiiv:
11 12 13 15 16 17 18 19

Mõista teisi sorteerimisalgoritme

Sorteerimine on programmeerimisel üks enim kasutatavaid algoritme. Elemente saab sorteerida erinevates programmeerimiskeeltes, kasutades erinevaid sorteerimisalgoritme, nagu kiire sortimine, mullide sortimine, ühendamise sortimine, sisestamise sortimine jne.

Mullide sortimine on parim valik, kui soovite õppida lihtsaima sorteerimise algoritmi kohta.

E-post
Sissejuhatus mullide sorteerimise algoritmi

Bubble Sort algoritm: suurepärane sissejuhatus massiivide sorteerimisse.

Loe edasi

Seotud teemad
  • Programmeerimine
  • JavaScripti
  • Python
  • Kodeerimise õpetused
Autori kohta
Yuvraj Chandra (27 artiklit on avaldatud)

Yuvraj on arvutiteaduse eriala üliõpilane Delhis, Indias. Ta on kirglik Full Stacki veebiarenduse vastu. Kui ta ei kirjuta, uurib ta erinevate tehnoloogiate sügavust.

Veel Yuvraj Chandrast

Telli meie uudiskiri

Liituge meie uudiskirjaga, kus leiate tehnilisi näpunäiteid, ülevaateid, tasuta e-raamatuid ja eksklusiivseid pakkumisi!

Veel üks samm !!!

Palun kinnitage oma e-posti aadress e-kirjas, mille teile just saatsime.

.