Bevezetés a Merge Sort algoritmusba

A Merge sort egy rendezési algoritmus, amely az "ossza és hódítsa" technikán alapul. Ez az egyik leghatékonyabb rendezési algoritmus.

Ebben a cikkben megismerheti az egyesítés rendezésének algoritmusának működését, az egyesítés rendezésének algoritmusát, annak idő és tér bonyolultsága, és megvalósítása különféle programozási nyelveken, például C ++, Python és JavaScript.

Hogyan működik a Merge Sort algoritmus?

A Merge sort az ossza és hódítsa elven működik. Az egyesítés rendezése többszörösen tömböt oszt két egyenlő részsávra, mindaddig, amíg az egyes részrajzok egyetlen elemből állnak. Végül az összes részsávot egyesítik úgy, hogy a kapott tömb rendeződik.

Ez a koncepció hatékonyabban magyarázható egy példa segítségével. Vegyünk egy rendezetlen tömböt a következő elemekkel: {16, 12, 15, 13, 19, 17, 11, 18}.

Itt az egyesítés rendezési algoritmus két részre osztja a tömböt, felhívja magát a két félre, majd egyesíti a két rendezett felet.

Egyesítés rendezési algoritmus

Az alábbiakban olvasható az egyesítés rendezésének algoritmusa:

MergeSort (arr [], leftIndex, rightIndex)
ha leftIndex> = rightIndex
Visszatérés
más
Keresse meg a tömböt kétfelé osztó középső indexet: 
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
MergeSort () hívása az első félévben: 
MergeSort hívása (arr, leftIndex, middleIndex)
A mergeSort () hívása a második félidőre:
MergeSort hívása (arr, middleIndex + 1, rightIndex)
Egyesítse a 2. és 3. lépésben rendezett két felet:
Hívás egyesítése (arr, leftIndex, middleIndex, rightIndex)

Összefüggő: Mi a rekurzió és hogyan használod?

A Merge Sort algoritmus idő és tér komplexitása

Az Egyesítés rendezési algoritmus a következő ismétlődési összefüggés formájában fejezhető ki:

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

Miután megoldotta ezt az ismétlődési relációt a mester tétel vagy megismétlődési fa módszerrel, O (n logn) néven kapja meg a megoldást. Így az egyesítés rendezési algoritmus időbeli összetettsége az O (n logn).

Az egyesítési sorrend legjobb időbeli összetettsége: O (n logn)

Az egyesítés rendezésének átlagos eseti időbeli összetettsége: O (n logn)

Az egyesítés sorrendjének legrosszabb esete: O (n logn)

Összefüggő: Mi a Big-O jelölés?

A kiegészítő tér bonyolultsága az egyesítés rendezési algoritmusa az Tovább) mint n kiegészítő hely szükséges az egyesítési rendezés megvalósításában.

A Merge Sort algoritmus megvalósítása C ++

Az alábbiakban olvasható az egyesítés rendezési algoritmus C ++ megvalósítása:

// a C ++ megvalósítása
// egyesítési algoritmus egyesítése
#include 
névtér használata std;
// Ez a függvény egyesíti az arr [] két részsávját
// Bal alrajz: arr [leftIndex..middleIndex]
// Jobb alrét: arr [middleIndex + 1..rightIndex]
void egyesítés (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Ideiglenes tömbök létrehozása
int L [leftSubarraySize], R [rightSubarraySize];
// Adatok másolása ideiglenes tömbökbe L [] és R []
for (int i = 0; i L [i] = arr [leftIndex + i];
for (int j = 0; j R [j] = arr [middleIndex + 1 + j];
// Egyesítse az ideiglenes tömböket arr-ba [leftIndex..rightIndex]
// A bal oldali rész kezdeti indexe
int i = 0;
// A Right alrész kezdeti indexe
int j = 0;
// Összevont részrajz kezdeti indexe
int k = leftIndex;
while (i {
ha (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
más
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Ha van még néhány elem az L [] -ban
// Másolás arr-be []
míg (i {
arr [k] = L [i];
i ++;
k ++;
}
// Ha van még néhány elem az R-ben []
// Másolás arr-be []
míg (j {
arr [k] = R [j];
j ++;
k ++;
}
}
void mergeSort (int arr [], int leftIndex, int rightIndex)
{
if (leftIndex> = rightIndex)
{
Visszatérés;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
egyesítés (arr, leftIndex, middleIndex, rightIndex);
}
// Funkció az elemek kinyomtatásához
a tömb //
void printArray (int arr [], int méret)
{
for (int i = 0; i {
cout << arr [i] << "";
}
cout << endl;
}
// Illesztőprogram-kód
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int size = sizeof (arr) / sizeof (arr [0]);
cout << "Válogatás nélküli tömb:" << endl;
printArray (arr, méret);
mergeSort (arr, 0, méret - 1);
cout << "Rendezett tömb:" << endl;
printArray (arr, méret);
visszatér 0;
}

Kimenet:

Válogatás nélküli tömb:
16 12 15 13 19 17 11 18 
Rendezett tömb:
11 12 13 15 16 17 18 19

A Merge Sort algoritmus JavaScript megvalósítása

Az alábbiakban olvasható az egyesítés rendezése algoritmus JavaScript-implementációja:

// a JavaScript JavaScript implementációja
// egyesítési algoritmus egyesítése
// Ez a függvény egyesíti az arr [] két részsávját
// Bal alrajz: arr [leftIndex..middleIndex]
// Jobb alrét: arr [middleIndex + 1..rightIndex]
függvény egyesítése (arr, leftIndex, middleIndex, rightIndex) {
hagyjuk leftSubarraySize = middleIndex - leftIndex + 1;
hadd rightSubarraySize = rightIndex - middleIndex;
// Ideiglenes tömbök létrehozása
var L = új tömb (leftSubarraySize);
var R = új tömb (rightSubarraySize);
// Adatok másolása ideiglenes tömbökbe L [] és R []
for (legyen i = 0; énL [i] = arr [leftIndex + i];
}
for (legyen j = 0; jR [j] = arr [middleIndex + 1 + j];
}
// Egyesítse az ideiglenes tömböket arr-ba [leftIndex..rightIndex]
// A bal oldali rész kezdeti indexe
var i = 0;
// A Right alrész kezdeti indexe
var j = 0;
// Összevont részrajz kezdeti indexe
var k = leftIndex;
while (i {
ha (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
más
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Ha van még néhány elem az L [] -ban
// Másolás arr-be []
míg (i {
arr [k] = L [i];
i ++;
k ++;
}
// Ha van még néhány elem az R-ben []
// Másolás arr-be []
míg (j {
arr [k] = R [j];
j ++;
k ++;
}
}
függvény mergeSort (arr, leftIndex, rightIndex) {
if (leftIndex> = rightIndex) {
Visszatérés
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
egyesítés (arr, leftIndex, middleIndex, rightIndex);
}
// Funkció az elemek kinyomtatásához
a tömb //
függvény printArray (arr, méret) {
for (legyen i = 0; éndocument.write (arr [i] + "");
}
document.write ("
");
}
// Illesztőprogram kódja:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var size = arr.length;
document.write ("Nem rendezett tömb:
");
printArray (arr, méret);
mergeSort (arr, 0, méret - 1);
document.write ("Rendezett tömb:
");
printArray (arr, méret);

Kimenet:

Válogatás nélküli tömb:
16 12 15 13 19 17 11 18
Rendezett tömb:
11 12 13 15 16 17 18 19

Összefüggő: Dinamikus programozás: Példák, gyakori problémák és megoldások

A Merge Sort algoritmus Python megvalósítása

Az alábbiakban olvasható az egyesítés rendezése algoritmus Python-megvalósítása:

# A Python implementációja
# egyesítés rendezési algoritmus
def mergeSort (arr):
ha len (arr)> 1:
# A tömb középső indexének megkeresése
middleIndex = len (arr) // 2
# A tömb bal fele
L = arr [: middleIndex]
# A tömb jobb fele
R = arr [middleIndex:]
# A tömb első felének rendezése
mergeSort (L)
# A tömb második felének rendezése
mergeSort (R)
# A bal alrész kezdeti indexe
i = 0
# A Right alrész kezdeti indexe
j = 0
# Az egyesített alrész kezdeti indexe
k = 0
# Adatok másolása az L [] és az R [] hőmérséklet tömbökbe
míg i ha L [i] arr [k] = L [i]
i = i + 1
más:
arr [k] = R [j]
j = j + 1
k = k + 1
# Annak ellenőrzése, hogy van-e még néhány elem
míg i arr [k] = L [i]
i = i + 1
k = k + 1
míg j arr [k] = R [j]
j = j + 1
k = k + 1
# Funkció az elemek kinyomtatására
a tömb #
def printArray (arr, méret):
i tartományban (méret):
nyomtatás (arr [i], end = "")
nyomtatás()
# Illesztőprogram-kód
arr = [16, 12, 15, 13, 19, 17, 11, 18]
méret = len (arr)
nyomtatás ("Rendetlen tömb:")
printArray (arr, méret)
mergeSort (arr)
nyomtatás ("Rendezett tömb:")
printArray (arr, méret)

Kimenet:

Válogatás nélküli tömb:
16 12 15 13 19 17 11 18
Rendezett tömb:
11 12 13 15 16 17 18 19

A többi rendezési algoritmus megértése

A rendezés az egyik leggyakrabban használt algoritmus a programozásban. Különféle rendezési algoritmusok segítségével rendezheti az elemeket különböző programozási nyelveken, például gyors rendezés, buborék rendezés, egyesítés rendezés, beszúrás rendezés stb.

A buborék rendezése a legjobb választás, ha meg akarja ismerni a legegyszerűbb rendezési algoritmust.

Bevezetés a Bubble Sort algoritmusba

A Bubble Sort algoritmus: kiváló bevezetés a tömbök rendezésébe.

Olvassa el a következőt

A szerzőről