Алгоритм сортування злиття

У цьому підручнику ви дізнаєтеся про сортування злиття. Крім того, ви знайдете робочі приклади злиття сорту C, C ++, Java та Python.

Сортування злиття - це один з найпопулярніших алгоритмів сортування, який базується на принципі Divide and Conquer Algorithm.

Тут проблема поділяється на кілька підзадач. Кожна підзадача вирішується індивідуально. Нарешті, підзадачі об’єднуються, щоб сформувати остаточне рішення.

Приклад сортування злиття

Стратегія поділу та завоювання

Використовуючи техніку « Розділи і завоюй» , ми ділимо задачу на підзадачі. Коли рішення для кожної підзадачі готове, ми «поєднуємо» результати з підзадач для вирішення основної проблеми.

Припустимо, нам довелося сортувати масив А. Підзадача полягала б у сортуванні підрозділу цього масиву, починаючи з індексу p і закінчуючи індексом r, позначеним як A (p… r).

Поділити
Якщо q - точка на півдорозі між p і r, тоді ми можемо розділити підмасив A (p… r) на два масиви A (p… q) і A (q + 1, r).

Conquer
На етапі conquer ми намагаємося відсортувати як підмасиви A (p… q), так і A (q + 1, r). Якщо ми ще не досягли базового випадку, ми знову ділимо обидва ці підмасиви і намагаємося їх відсортувати.

Поєднання
Коли крок завоювання досягає базового кроку, і ми отримуємо два відсортовані підмасиви A (p… q) і A (q + 1, r) для масиву A (p… r), ми об’єднуємо результати, створюючи відсортований масив A ( p… r) з двох відсортованих підмасивів A (p… q) та A (q + 1, r).

Алгоритм злиття

Функція MergeSort неодноразово ділить масив на дві половини, поки ми не дійдемо до етапу, коли ми намагатимемося виконати MergeSort на підмасиві розміром 1, тобто p == r.

Після цього в гру вступає функція злиття, яка об’єднує відсортовані масиви у більші масиви, доки весь масив не буде об’єднаний.

 MergeSort (A, p, r): якщо p> r повертає q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) злиття (A, p, q, r )

Щоб відсортувати цілий масив, нам потрібно зателефонувати MergeSort(A, 0, length(A)-1).

Як показано на зображенні нижче, алгоритм сортування злиття рекурсивно ділить масив на половинки, поки ми не дійдемо до базового випадку масиву з 1 елементом. Після цього функція злиття забирає відсортовані підмасиви та об’єднує їх, щоб поступово сортувати весь масив.

Об’єднати сортування в дії

Злиття Крок Merge Sort

Кожен рекурсивний алгоритм залежить від базового випадку та можливості комбінувати результати з базових випадків. Сортування злиття не відрізняється. Найважливіша частина алгоритму сортування злиття - це, як ви вже здогадалися, крок злиття.

Крок злиття - це рішення простої проблеми об’єднання двох відсортованих списків (масивів) для побудови одного великого відсортованого списку (масиву).

Алгоритм підтримує три покажчики, по одному для кожного з двох масивів і одного для підтримання поточного індексу остаточного відсортованого масиву.

Ми дійшли до кінця будь-якого з масивів? Ні.
Крок об’єднання

Написання кодексу алгоритму злиття

Помітна різниця між описаним вище кроком злиття та тим, який ми використовуємо для сортування злиття, полягає в тому, що ми виконуємо функцію злиття лише на послідовних підмасивах.

Ось чому нам потрібен лише масив, перша позиція, останній індекс першого підмасиву (ми можемо обчислити перший індекс другого підмасиву) та останній індекс другого підмасиву.

Наше завдання - об’єднати два підмасиви A (p… q) і A (q + 1… r), щоб створити відсортований масив A (p… r). Отже, вхідними даними для функції є A, p, q і r

Функція злиття працює наступним чином:

  1. Створіть копії підмасивів L ← A(p… q)та M ← A (q + 1… r).
  2. Створіть три покажчики i, j та k
    1. я підтримую поточний індекс L, починаючи з 1
    2. j підтримує поточний індекс М, починаючи з 1
    3. k підтримує поточний індекс A (p… q), починаючи з p.
  3. Поки ми не дійдемо до кінця L або M, виберіть більший з елементів з L і M і поставте їх у правильному положенні в A (p… q)
  4. Коли в нас закінчуються елементи в L або M, підберіть решту елементів і поставте в A (p… q)

У коді це виглядатиме так:

 // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) )

Функція злиття (), пояснювана поетапно

У цій функції відбувається багато чого, тож давайте візьмемо приклад, щоб побачити, як це буде працювати.

Як завжди, картинка говорить тисячу слів.

Об'єднання двох послідовних підмасивів масиву

Масив A (0… 5) містить два відсортовані підмасиви A (0… 3) і A (4… 5). Давайте подивимося, як функція злиття об’єднає два масиви.

 void merge(int arr(), int p, int q, int r) ( // Here, p = 0, q = 4, r = 6 (size of array)

Крок 1: Створіть повторювані копії підмасивів для сортування

  // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1 = 3 - 0 + 1 = 4; int n2 = r - q = 5 - 3 = 2; int L(4), M(2); for (int i = 0; i < 4; i++) L(i) = arr(p + i); // L(0,1,2,3) = A(0,1,2,3) = (1,5,10,12) for (int j = 0; j < 2; j++) M(j) = arr(q + 1 + j); // M(0,1,2,3) = A(4,5) = (6,9)
Створіть копії підмасивів для злиття

Крок 2: Підтримуйте поточний індекс підмасивів та основного масиву

  int i, j, k; i = 0; j = 0; k = p;
Зберігати індекси копій підмасиву та основного масиву

Крок 3: Поки ми не дійдемо до кінця L або M, виберіть більший серед елементів L і M і розмістіть їх у правильному положенні в A (p… r)

  while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; )
Порівнюючи окремі елементи відсортованих підмасивів, поки не дійдемо до кінця одного

Крок 4: Коли в нас закінчуються елементи в L або M, підберіть решту елементів і поставте в A (p… r)

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Скопіюйте решту елементів з першого масиву в основний підмасив 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Скопіюйте інші елементи другого масиву в основний підмасив

Цей крок був би потрібен, якби розмір M був більшим за L.

В кінці функції злиття сортується підмасив A (p… r).

Приклади Python, Java та C / C ++

Python Java C C ++ 
 # MergeSort in Python def mergeSort(array): if len(array)> 1: # r is the point where the array is divided into two subarrays r = len(array)//2 L = array(:r) M = array(r:) # Sort the two halves mergeSort(L) mergeSort(M) i = j = k = 0 # Until we reach either end of either L or M, pick larger among # elements L and M and place them in the correct position at A(p… r) while i < len(L) and j < len(M): if L(i) < M(j): array(k) = L(i) i += 1 else: array(k) = M(j) j += 1 k += 1 # When we run out of elements in either L or M, # pick up the remaining elements and put in A(p… r) while i < len(L): array(k) = L(i) i += 1 k += 1 while j < len(M): array(k) = M(j) j += 1 k += 1 # Print the array def printList(array): for i in range(len(array)): print(array(i), end=" ") print() # Driver program if __name__ == '__main__': array = (6, 5, 12, 10, 9, 1) mergeSort(array) print("Sorted array is: ") printList(array) 
 // Merge sort in Java class MergeSort ( // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L() = new int(n1); int M() = new int(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = (l + r) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver program public static void main(String args()) ( int arr() = ( 6, 5, 12, 10, 9, 1 ); MergeSort ob = new MergeSort(); ob.mergeSort(arr, 0, arr.length - 1); System.out.println("Sorted array:"); printArray(arr); ) )
 // Merge sort in C #include // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) printf("%d ", arr(i)); printf(""); ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); printf("Sorted array: "); printArray(arr, size); )
 // Merge sort in C++ #include using namespace std; // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) cout << arr(i) << " "; cout << endl; ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); cout << "Sorted array: "; printArray(arr, size); return 0; )

Складність сортування об’єднати

Складність часу

Складність найкращого випадку: O (n * log n)

Найгірша складність: O (n * log n)

Середня складність справи: O (n * log n)

Складність простору

Космічна складність злиття сортує O (n).

Об’єднати сортувальні програми

  • Проблема підрахунку інверсії
  • Зовнішнє сортування
  • Додатки для електронної комерції

Цікаві статті...