Сортування злиття на Java

1. Вступ

У цьому підручнику ми розглянемо алгоритм злиття сортування та його реалізацію на Java .

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

2. Алгоритм

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

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

Алгоритм можна охарактеризувати як наступний двоетапний процес:

  • Розділити: На цьому кроці ми ділимо вхідний масив на 2 половини , опорна точка - це середина масиву. Цей крок виконується рекурсивно для всіх половинних масивів, поки не залишиться більше половинних масивів для поділу.
  • Conquer: На цьому кроці ми сортуємо та об’єднуємо розділені масиви знизу вгору і отримуємо відсортований масив.

На наступній діаграмі показано повний процес сортування злиття для прикладу масиву {10, 6, 8, 5, 7, 3, 4}.

Якщо ми уважніше розглянемо діаграму, то побачимо, що масив рекурсивно ділиться на дві половини, доки розмір не стає 1. Як тільки розмір стає 1, процеси злиття починають діяти і починають зливати масиви назад під час сортування:

3. Впровадження

Для реалізації ми напишемо функцію mergeSort, яка бере як вхідний масив і його довжину як параметри. Це буде рекурсивна функція, тому нам потрібні база та рекурсивні умови.

Базова умова перевіряє, чи довжина масиву дорівнює 1, і він просто повернеться. В інших випадках рекурсивний виклик буде виконаний.

Для рекурсивного випадку ми отримуємо середній індекс і створюємо два тимчасові масиви l [] і r [] . Потім функція mergeSort викликається рекурсивно для обох підмасивів :

public static void mergeSort(int[] a, int n) { if (n < 2) { return; } int mid = n / 2; int[] l = new int[mid]; int[] r = new int[n - mid]; for (int i = 0; i < mid; i++) { l[i] = a[i]; } for (int i = mid; i < n; i++) { r[i - mid] = a[i]; } mergeSort(l, mid); mergeSort(r, n - mid); merge(a, l, r, mid, n - mid); }

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

Функція злиття порівнює елементи обох підмасивів по одному і поміщає менший елемент у вхідний масив.

Коли ми досягаємо кінця одного з підмасивів, решта елементів з іншого масиву копіюються у вхідний масив, отримуючи таким чином остаточний відсортований масив:

public static void merge( int[] a, int[] l, int[] r, int left, int right) { int i = 0, j = 0, k = 0; while (i < left && j < right) { if (l[i] <= r[j]) { a[k++] = l[i++]; } else { a[k++] = r[j++]; } } while (i < left) { a[k++] = l[i++]; } while (j < right) { a[k++] = r[j++]; } } 

Одиничний тест для програми:

@Test public void positiveTest() { int[] actual = { 5, 1, 6, 2, 3, 4 }; int[] expected = { 1, 2, 3, 4, 5, 6 }; MergeSort.mergeSort(actual, actual.length); assertArrayEquals(expected, actual); }

4. Складність

Оскільки сортування злиттям є рекурсивним алгоритмом, складність часу може бути виражена як таке рекурсивне відношення:

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

2T (n / 2) відповідає часу, необхідному для сортування підмасивів, та O (n) часу для злиття всього масиву.

Після вирішення складність часу прийде до O (nLogn).

Це справедливо для гіршого, середнього та найкращого випадку, оскільки він завжди буде ділити масив на два, а потім об'єднувати.

Складність простору алгоритму дорівнює O (n), оскільки ми створюємо тимчасові масиви в кожному рекурсивному виклику.

5. Висновок

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

Весь робочий код доступний на GitHub.