Sortowanie przez scalanie
Sortowanie przez scalanie to wydajny algorytm sortowania, ale koncepcyjnie jest bardziej złożony niż algorytmy sortowania przez wstawianie lub wybieranie. Algorytm ten dzieli tablicę na dwie podtablice o równych rozmiarach, sortuje każdą z nich, a następnie scala je w jedną większą. W przypadku nieparzystej liczby elementów jedna z podtablic zawiera o jeden element więcej niż druga.
Implementacja sortowania przez scalanie z przykładu jest rekurencyjna. Przypadek bazowy to tablica z jednym elementem, czyli jest z definicji posortowana, więc wynik jest zwracany od razu. Krok rekurencyjny dzieli tablicę na dwie potencjalnie równe części, rekurencyjnie je sortuje, a następnie łączy wyniki w jedną, większą i posortowaną tablicę.
Przypuśćmy, że algorytm wykonał już mniejsze podziały, sortowania i scalenia, uzyskując posortowane tablice A:
i B:
Sortowanie przez scalanie łączy te dwie tablice w jedną, większą. Najmniejszym elementem w A jest 4 (zerowy indeks w A). Najmniejszym elementem w B jest 5 (zerowy indeks w B). Aby określić najmniejszy element w większej tablicy, algorytm porównuje 4 i 5. Wartość z A jest mniejsza, więc 4 staje się pierwszym elementem połączonych tablic. Algorytm porównuje teraz 10 (drugi element z A) i 5 (pierwszy element z B). Wartość 5 jest mniejsza, więc trafia do wynikowej tablicy jako drugi element. Teraz algorytm porównuje 10 i 30, więc 10 staje się trzecim elementem tablicy.
Implementacja algorytmu sortowania przez scalanie
Rysunek 19.6 deklaruje klasę MergeSortTest, która zawiera:
- metodę statyczną mergeSort, która zainicjalizuje sortowanie tablicy wartości int za pomocą algorytmu sortowania przez scalanie;
- metodę statyczną sortArray, która wykona rekurencyjny algorytm sortowania — tę metodę wywołuje metoda mergeSort;
- metodę statyczną merge, która łączy dwie posortowane podtablice w jedną posortowaną tablicę;
- metodę statyczną subarrayString, która wyświetla tekstową reprezentację podtablicy;
- metodę main do testowania metody mergeSort.
2 // Sortowanie przez scalanie
3 import java.security.SecureRandom;
4 import java.util.Arrays;
5
6 public class MergeSortTest {
7 // Wywołaj rekurencyjną metodę sortArray, aby rozpocząć sortowanie
8 public static void mergeSort(int[] data) {
9 sortArray(data, 0, data.length - 1); // Sortuj całą tablicę.
10 }
11
12 // Dzieli tablicę, sortuje podtablice i scala posortowane podtablice
13 private static void sortArray(int[] data, int low, int high) {
14 // Sprawdź przypadek bazowy, czyli tablicę o rozmiarze 1
15 if ((high - low) >= 1) { // Jeśli to nie przypadek bazowy
16 int middle1 = (low + high) / 2; // Oblicz środek tablicy
17 int middle2 = middle1 + 1; // Oblicz następny element po środku
18
19 // Wyświetl krok podziału
20 System.out.printf("Podział: %s%n",
21 subarrayString(data, low, high));
22 System.out.printf(" %s%n",
23 subarrayString(data, low, middle1));
24 System.out.printf(" %s%n%n",
25 subarrayString(data, middle2, high));
26
27 // Podziel tablicę na pół; posortuj każdą połowę (wywołania rekurencyjne)
28 sortArray(data, low, middle1); // Pierwsza połowa tablicy
29 sortArray(data, middle2, high); // Druga połowa tablicy
30
31 // Złączenie dwóch posortowanych przed powrotem
32 merge (data, low, middle1, middle2, high); 33 }
33 }
34 }
35
36 // Scalenie dwóch posortowanych podtablic w jedną posortowaną tablicę
37 private static void merge(int[] data, int left, int middle1,
38 int middle2, int right) {
39
40 int leftIndex = left; // Indeks dla lewej podtablicy
41 int rightIndex = middle2; // Indeks dla prawej podtablicy
42 int combinedIndex = left; // Indeks dla tablicy tymczasowej
43 int[] combined = new int[data.length]; // Tablica robocza
44
45 // Wyświetl dwie podtablice przed scaleniem
46 System.out.printf("Scalenie: %s%n",
47 subarrayString(data, left, middle1));
48 System.out.printf(" %s%n",
49 subarrayString(data, middle2, right));
50
51 // Scalanie aż do osiągnięcia końca którejkolwiek z nich
52 while (leftIndex <= middle1 && rightIndex <= right) {
53 // Umieść mniejszy z dwóch aktualnych elementów jako wynik
54 // i przejdź do następnego miejsca
55 if (data[leftIndex] <= data[rightIndex]) {
56 combined[combinedIndex++] = data[leftIndex++];
57 }
58 else {
59 combined[combinedIndex++] = data[rightIndex++];
60 }
61 }
62
63 // Jeśli lewa tablica jest pusta…
64 if (leftIndex == middle2) {
65 // skopiuj pozostałą część prawej tablicy
66 while (rightIndex <= right) {
67 combined[combinedIndex++] = data[rightIndex++];
68 }
69 }
70 else { // Jeśli prawa tablica jest pusta…
71 // skopiuj pozostałą część lewej tablicy
72 while (leftIndex <= middle1) {
73 combined[combinedIndex++] = data[leftIndex++];
74 }
75 }
76
77 // Skopiuj wartości do pierwotnej tablicy
78 for (int i = left; i <= right; i++) {
79 data[i] = combined[i];
80 }
81
82 // Wyświetl scaloną tablicę
83 System.out.printf(" %s%n%n",
84 subarrayString(data, left, right));
85 }
86
87 // Metoda wyświetlająca pewne wartości z tablicy
88 private static String subarrayString(int[] data, int low, int high) { 89 StringBuilder temporary = new StringBuilder();
89 StringBuilder temporary = new StringBuilder();
90
91 // Użyj spacji do wyrównania
92 for (int i = 0; i < low; i++) {
93 temporary.append(" ");
94 }
95
96 // Wyświetl elementy pozostałe w tablicy
97 for (int i = low; i <= high; i++) {
98 temporary.append(" " + data[i]);
99 }
100
101 return temporary.toString();
102 }
103
104 public static void main(String[] args) {
105 SecureRandom generator = new SecureRandom();
106
107 // Utwórz nieposortowaną tablicę 10 liczb losowych
108 int[] data = generator.ints(10, 10, 91).toArray();
109
110 System.out.printf("Tablica nieposortowana: %s%n%n", Arrays.toString(data));
111 mergeSort(data); // Sortowanie tablicy
112 System.out.printf("Tablica posortowana: %s%n", Arrays.toString(data));
113 }
114 }
Podział: 75 56 85 90 49 26 12 48 40 47
75 56 85 90 49
26 12 48 40 47
Podział: 75 56 85 90 49
75 56 85
90 49
Podział: 75 56 85
75 56
85
Podział: 75 56
75
56
Scalenie: 75
56
56 75
Scalenie: 56 75
85
56 75 85
Podział: 90 49
90
49
Scalenie: 90
49
49 90
Scalenie: 56 75 8549 90
49 56 75 85 90
Podział: 26 12 48 40 47
26 12 48
40 47
Podział: 26 12 48
26 12
48
Podział: 26 12
26
12
Scalenie: 26
12
12 26
Scalenie: 12 26
48
12 26 48
Podział: 40 47
40
47
Scalenie: 40
47
40 47
Scalenie: 12 26 48
40 47
12 26 40 47 48
Scalenie: 49 56 75 85 90
12 26 40 47 48
12 26 40 47 48 49 56 75 85 90
Tablica posortowana: [12, 26, 40, 47, 48, 49, 56, 75, 85, 90]
Rysunek 19.6. Sortowanie przez scalanie
Metoda main (wiersze od 104. do 113.) jest taka sama jak na rysunkach 19.4 i 19.5, ale w wierszu 111. wywołuje metodę mergeSort, aby posortować elementy tablicy w porządku rosnącym. Wynik działania programu przedstawia podziały i scalenia wykonywane przy sortowaniu, co pozwala dobrze poznać każdy krok algorytmu. Warto przeanalizować wyniki krok po kroku, aby w pełni zrozumieć ten elegancki algorytm sortowania.
Metoda mergeSort
Wiersze od 8. do 10. z rysunku 19.6 deklarują metodę mergeSort. Wiersz 9. wywołuje metodę sortArray z wartościami 0 i data.length - 1 jako argumenty. Odpowiada to indeksom początku i końca całej sortowanej tablicy. Wartości te powodują,
że metoda sortArray posortuje wszystkie elementy.
Rekurencyjna metoda sortArray
Metoda sortArray (wiersze od 13. do 34.) wykonuje rekurencyjny algorytm sortowania przez scalanie. Wiersz 15. testuje przypadek bazowy. Jeśli rozmiar tablicy wynosi 1, tablica jest już posortowana, więc metoda od razu się kończy. Jeśli rozmiar tablicy jest większy od 1, metoda dzieli tablicę na dwie podtablice, wywołując metodę sortArray do posortowania każdej podtablicy, a następnie złączenia wyników. Wiersz 28. wywołuje metodę sortArray dla pierwszej połowy tablicy, a wiersz 29. dla drugiej połowy tablicy. Po powrocie z metod obiepodtablice są posortowane. Wiersz 32. wywołuje metodę merge (wiersze od 37. do 85.) na obu połówkach, aby połączyć je w jedną, posortowaną tablicę.
Metoda merge
Wiersze od 37. do 85. deklarują metodę merge. Wiersze od 52. do 61. wykonują pętlę aż do osiągnięcia którejkolwiek z podtablic. Wiersz 55. sprawdza, który z elementów na początku tablic jest mniejszy. Jeśli element lewej tablicy jest mniejszy, wiersz 56. umieszcza tę wartość w połączonej tablicy. Jeśli element prawej tablicy jest mniejszy, wiersz 59. umieszcza tę wartość w połączonej tablicy. Gdy pętla while się zakończy, jedna z podtablic będzie w całości przeniesiona do połączonej tablicy. Wiersz 64. sprawdza, czy to lewa tablica osiągnęła koniec. Jeśli tak, wiersze od 66. do 68. wypełniają połączoną tablicę elementami prawej tablicy. Jeśli lewa tablica nie osiągnęła końca, musiała to zrobić prawa, więc wiersze od 72. do 74. wypełniają połączoną tablicę elementami lewej tablicy. Na końcu wiersze od 78. do 80. kopiują połączoną tablicę do oryginalnej tablicy.
Wydajność sortowania przez scalanie
Sortowanie przez scalanie jest zdecydowanie bardziej wydajne niż którekolwiek z dwóch poprzednich. Przyjrzyjmy się pierwszemu (nierekurencyjnemu) wywołaniu sortArray. Jego wynikiem są dwa następne wywołania sortArray, ale dla tablic o mniej więcej połowie rozmiaru oryginalnej tablicy. Dodatkowo pojawia się wywołanie metody merge, która w najgorszym przypadku wymaga n – 1 porównań, aby wypełnić oryginalną tablicę, co daje O(n). (Przypomnijmy, że element tablicy wybieramy, porównując elementy z obu podtablic). Dwa wywołania sortArray powodują cztery wywołania rekurencyjne sortArray dla tablic będących ćwiartkami oryginalnej tablicy. Każde z tych wywołań to również operacja merge, która w najgorszym razie wymaga n/2 – 1 porównań, czyli ponownie O(n). Proces jest kontynuowany i za każdym razem z jednego wywołania otrzymujemy dwa wywołania sortArray i jedno merge aż o momentu dojścia do podtablic jednoelementowych. Na każdym poziomie potrzeba O(n) operacji do scalenia podtablic.
Każdy podział dzieli tablicę na pół, więc podwojenie rozmiaru wymaga dodatkowego poziomu. Czterokrotnie większa tablica wymaga tylko dwóch dodatkowych poziomów. Wzorzec ten jest logarytmiczny, więc otrzymujemy log2 n poziomów. Uzyskujemy więc łączną wydajność wynoszącą O(n log n).
Programowanie w Javie. Solidna wiedza w praktyce. Wydanie XI, Autorzy: Paul Deitel, Harvey Deitel, Wydawnictwo: Helion
