Merge sort е алгоритъм за сортиране, базиран на техниката „разделяй и владей“. Това е един от най-ефективните алгоритми за сортиране.
В тази статия ще научите за работата на алгоритъма за сортиране на сливане, алгоритъма на сортирането на сливането, неговите сложност във времето и пространството и прилагането му в различни езици за програмиране като C ++, Python и JavaScript.
Как работи алгоритъмът за сортиране на обединяване?
Сливането на обединяване работи на принципа на разделяй и владей. Сливането на обединяване многократно разделя масив на два равни подмасива, докато всеки подмасив се състои от един елемент. И накрая, всички тези подредове се обединяват така, че полученият масив се сортира.
Тази концепция може да бъде обяснена по-ефективно с помощта на пример. Помислете за несортиран масив със следните елементи: {16, 12, 15, 13, 19, 17, 11, 18}.
Тук алгоритъмът за сортиране на сливане разделя масива на две половини, извиква себе си за двете половини и след това обединява двете сортирани половини.
Обединяване на алгоритъм за сортиране
По-долу е алгоритъмът за сортиране на сливането:
MergeSort (arr [], leftIndex, rightIndex)
ако leftIndex> = rightIndex
връщане
друго
Намерете средния индекс, който разделя масива на две половини:
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
Обадете се на mergeSort () за първата половина:
Извикайте mergeSort (arr, leftIndex, middleIndex)
Обадете се на mergeSort () за втората половина:
Извикайте mergeSort (arr, middleIndex + 1, rightIndex)
Обединете двете половини, сортирани в стъпки 2 и 3:
Обединяване на обаждания (arr, leftIndex, middleIndex, rightIndex)
Свързани: Какво представлява рекурсията и как я използвате?
Сложност във времето и пространството на алгоритъма за сортиране на обединяване
Алгоритъмът за сортиране Merge може да бъде изразен под формата на следната рецидивираща връзка:
T (n) = 2T (n / 2) + O (n)
След решаването на тази рекурентна връзка с помощта на теоремата на капитана или метода на дървото на рецидиви, ще получите решението като O (n logn). По този начин сложността на времето на алгоритъма за сортиране на сливане е O (n logn).
Най-добрата сложност във времето при сортирането на сливанията: O (n logn)
Средната сложност на времето на сортиране на сливането: O (n logn)
Сложността във времето в най-лошия случай на сортирането: O (n logn)
Свързани: Какво е Big-O нотация?
Сложността на спомагателното пространство на алгоритъма за сортиране на сливане е На) като н в изпълнението на сортиране на сливане се изисква помощно пространство.
C ++ Внедряване на алгоритъма за сортиране на обединяване
По-долу е C ++ изпълнението на алгоритъма за сортиране на сливане:
// C ++ изпълнение на
// обединяване на алгоритъм за сортиране
#include
използване на пространство от имена std;
// Тази функция обединява два подмасива на arr []
// Ляв подмасив: arr [leftIndex..middleIndex]
// Десен подмасив: arr [middleIndex + 1..rightIndex]
обединяване на невалидни (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Създаване на временни масиви
int L [leftSubarraySize], R [rightSubarraySize];
// Копиране на данни във временни масиви L [] и R []
за (int i = 0; i L [i] = arr [leftIndex + i];
за (int j = 0; j R [j] = arr [middleIndex + 1 + j];
// Обединяване на временните масиви обратно в arr [leftIndex..rightIndex]
// Първоначален индекс на ляв подмасив
int i = 0;
// Първоначален индекс на дясно подмасив
int j = 0;
// Първоначален индекс на обединен подмасив
int k = leftIndex;
докато (i {
ако (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
друго
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Ако има някои останали елементи в L []
// Копиране в arr []
докато (i {
arr [k] = L [i];
i ++;
k ++;
}
// Ако има някои останали елементи в R []
// Копиране в arr []
докато (j {
arr [k] = R [j];
j ++;
k ++;
}
}
void mergeSort (int arr [], int leftIndex, int rightIndex)
{
ако (leftIndex> = rightIndex)
{
връщане;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
обединяване (arr, leftIndex, middleIndex, rightIndex);
}
// Функция за отпечатване на елементите
// на масива
void printArray (int arr [], int размер)
{
за (int i = 0; i {
cout << arr [i] << "";
}
cout << endl;
}
// код на драйвера
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int size = sizeof (arr) / sizeof (arr [0]);
cout << "Несортиран масив:" << endl;
printArray (arr, размер);
mergeSort (arr, 0, размер - 1);
cout << "Сортиран масив:" << endl;
printArray (arr, размер);
връщане 0;
}
Изход:
Несортиран масив:
16 12 15 13 19 17 11 18
Сортиран масив:
11 12 13 15 16 17 18 19
Внедряване на JavaScript на алгоритъма за сортиране на обединяване
По-долу е представена JavaScript реализацията на алгоритъма за сортиране на сливане:
// JavaScript изпълнение на
// обединяване на алгоритъм за сортиране
// Тази функция обединява два подмасива на arr []
// Ляв подмасив: arr [leftIndex..middleIndex]
// Десен подмасив: arr [middleIndex + 1..rightIndex]
функция за сливане (arr, leftIndex, middleIndex, rightIndex) {
нека leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
// Създаване на временни масиви
var L = нов масив (leftSubarraySize);
var R = нов масив (rightSubarraySize);
// Копиране на данни във временни масиви L [] и R []
за (нека i = 0; iL [i] = arr [leftIndex + i];
}
за (нека j = 0; jR [j] = arr [middleIndex + 1 + j];
}
// Обединяване на временните масиви обратно в arr [leftIndex..rightIndex]
// Първоначален индекс на ляв подмасив
var i = 0;
// Първоначален индекс на дясно подмасив
var j = 0;
// Първоначален индекс на обединен подмасив
var k = leftIndex;
докато (i {
ако (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
друго
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Ако има някои останали елементи в L []
// Копиране в arr []
докато (i {
arr [k] = L [i];
i ++;
k ++;
}
// Ако има някои останали елементи в R []
// Копиране в arr []
докато (j {
arr [k] = R [j];
j ++;
k ++;
}
}
функция mergeSort (arr, leftIndex, rightIndex) {
ако (leftIndex> = rightIndex) {
връщане
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
обединяване (arr, leftIndex, middleIndex, rightIndex);
}
// Функция за отпечатване на елементите
// на масива
функция printArray (arr, размер) {
за (нека i = 0; idocument.write (arr [i] + "");
}
document.write ("
");
}
// код на драйвера:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var размер = arr.length;
document.write ("Несортиран масив:
");
printArray (arr, размер);
mergeSort (arr, 0, размер - 1);
document.write ("Сортиран масив:
");
printArray (arr, размер);
Изход:
Несортиран масив:
16 12 15 13 19 17 11 18
Сортиран масив:
11 12 13 15 16 17 18 19
Свързани: Динамично програмиране: примери, често срещани проблеми и решения
Внедряване на Python на алгоритъма за сортиране на обединяване
По-долу е приложена Python реализацията на алгоритъма за сортиране на сливане:
# Внедряване на Python на
# алгоритъм за сортиране на сливане
def mergeSort (arr):
ако len (arr)> 1:
# Намиране на средния индекс на масива
middleIndex = len (arr) // 2
# Лявата половина на масива
L = arr [: middleIndex]
# Дясната половина на масива
R = arr [среден индекс:]
# Сортиране на първата половина на масива
mergeSort (L)
# Сортиране на втората половина на масива
mergeSort (R)
# Първоначален индекс на ляв подмасив
i = 0
# Първоначален индекс на дясно подмасив
j = 0
# Първоначален индекс на обединен подмасив
k = 0
# Копиране на данни в временни масиви L [] и R []
докато i ако L [i] arr [k] = L [i]
i = i + 1
друго:
arr [k] = R [j]
j = j + 1
k = k + 1
# Проверка дали има останали елементи
докато i arr [k] = L [i]
i = i + 1
k = k + 1
докато j arr [k] = R [j]
j = j + 1
k = k + 1
# Функция за отпечатване на елементите
# от масива
def printArray (arr, размер):
за i в обхват (размер):
отпечатване (arr [i], end = "")
печат ()
# Код на драйвера
arr = [16, 12, 15, 13, 19, 17, 11, 18]
размер = len (arr)
print ("Несортиран масив:")
printArray (arr, размер)
mergeSort (arr)
print ("Сортиран масив:")
printArray (arr, размер)
Изход:
Несортиран масив:
16 12 15 13 19 17 11 18
Сортиран масив:
11 12 13 15 16 17 18 19
Разберете други алгоритми за сортиране
Сортирането е един от най-използваните алгоритми в програмирането. Можете да сортирате елементи в различни езици за програмиране, като използвате различни алгоритми за сортиране като бързо сортиране, сортиране с балончета, сортиране чрез сливане, сортиране при вмъкване и т.н.
Bubble sort е най-добрият избор, ако искате да научите за най-простия алгоритъм за сортиране.
Алгоритъмът за сортиране на балончета: отлично въведение в сортирането на масиви.
Прочетете Напред
- Програмиране
- JavaScript
- Python
- Уроци за кодиране
Yuvraj е студент по компютърни науки в Университета на Делхи, Индия. Той е запален по Full Stack Web Development. Когато не пише, той изследва дълбочината на различните технологии.
Абонирайте се за нашия бюлетин
Присъединете се към нашия бюлетин за технически съвети, рецензии, безплатни електронни книги и ексклузивни оферти!
Още една стъпка…!
Моля, потвърдете имейл адреса си в имейла, който току-що ви изпратихме.