Sortuj przez scalanie w Javie

1. Wstęp

W tym samouczku przyjrzymy się algorytmowi sortowania przez scalanie i jego implementacji w Javie .

Sortowanie przez scalanie jest jedną z najbardziej wydajnych technik sortowania i opiera się na paradygmacie „dziel i rządź”.

2. Algorytm

Sortowanie przez scalanie to algorytm „dziel i rządź”, w którym najpierw dzielimy problem na podproblemy. Gdy rozwiązania podproblemów są gotowe, łączymy je razem, aby uzyskać ostateczne rozwiązanie problemu.

Jest to jeden z algorytmów, który można łatwo zaimplementować za pomocą rekurencji, ponieważ zajmujemy się podproblemami, a nie głównym problemem.

Algorytm można opisać jako następujący dwuetapowy proces:

  • Dzielenie: w tym kroku dzielimy tablicę wejściową na dwie połowy , przy czym oś jest środkiem tablicy. Ten krok jest wykonywany rekurencyjnie dla wszystkich pół macierzy, dopóki nie będzie już więcej pół macierzy do podziału.
  • Podbij: na tym etapie sortujemy i scalamy podzielone tablice od dołu do góry i otrzymujemy posortowaną tablicę.

Poniższy diagram przedstawia pełny proces sortowania przez scalanie dla przykładowej tablicy {10, 6, 8, 5, 7, 3, 4}.

Jeśli przyjrzymy się bliżej diagramowi, zobaczymy, że tablica jest rekurencyjnie dzielona na dwie połowy, aż rozmiar osiągnie 1. Gdy rozmiar osiągnie 1, zaczynają działać procesy scalania i rozpoczynają scalanie tablic z powrotem podczas sortowania:

3. Wdrożenie

Dla realizacji, będziemy pisać do mergesort funkcję, która trwa w tablicy wejściowej i jego długości jako parametrów. Będzie to funkcja rekurencyjna, więc potrzebujemy podstawy i warunków rekurencyjnych.

Warunek podstawowy sprawdza, czy długość tablicy wynosi 1 i po prostu zwróci. W pozostałych przypadkach wywołanie rekurencyjne zostanie wykonane.

W przypadku rekurencyjnym otrzymujemy indeks środkowy i tworzymy dwie tymczasowe tablice l [] i r [] . Następnie funkcja mergeSort jest wywoływana rekurencyjnie dla obu pod-tablic:

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); }

Następnie wywołujemy funkcję merge, która przyjmuje dane wejściowe i obie tablice podrzędne oraz indeksy początkowy i końcowy obu tablic podrzędnych .

Funkcja merge porównuje elementy obu tablic podrzędnych jeden po drugim i umieszcza mniejszy element w tablicy wejściowej.

Kiedy docieramy do końca jednej z pod-tablic, pozostałe elementy z drugiej tablicy są kopiowane do tablicy wejściowej, dając nam w ten sposób ostateczną posortowaną tablicę:

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 jednostkowy programu:

@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. Złożoność

Ponieważ sortowanie przez scalanie jest algorytmem rekurencyjnym, złożoność czasową można wyrazić jako następującą relację rekurencyjną:

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

2T (n / 2) odpowiada czasowi wymaganemu do posortowania pod-tablic i O (n) czasowi scalenia całej tablicy.

Po rozwiązaniu złożoność czasowa osiągnie O (nLogn).

Dotyczy to najgorszego, średniego i najlepszego przypadku, ponieważ zawsze dzieli tablicę na dwie części, a następnie łączy.

Złożoność przestrzeni algorytmu wynosi O (n), ponieważ tworzymy tymczasowe tablice w każdym wywołaniu rekurencyjnym.

5. Wniosek

W tym krótkim samouczku zobaczyliśmy, jak działa algorytm sortowania przez scalanie i jak możemy go zaimplementować w Javie.

Cały działający kod jest dostępny na GitHub.