Sortowanie przez Scalanie (ang. Merge Sort) – Jednym z podstawowych zagadnień w programowaniu jest sortowanie danych. Bez względu na to, czy jesteś początkującym programistą, czy po prostu chcesz dowiedzieć się więcej o algorytmach sortowania, w tym artykule zgłębimy temat Merge Sort, czyli Sortowania przez Scalanie.
Spis treści
Merge sort – wprowadzenie
Z tego materiału dowiesz się:
- Co to jest oraz jak działa Merge Sort?
- Na czym polega koncepcja dziel i zwyciężaj?
- Jak zaimplementować sortowanie Merge Sort?
Merge Sort – Sortowanie przez Scalanie
Merge Sort – to jeden z efektywnych algorytmów sortowania, który bazuje na koncepcji „Dziel i Zwyciężaj”.
Algorytm ten jest powszechnie stosowany w praktyce, ze względu na swoją wydajność i stabilność.
Dziel i zwyciężaj
Koncepcja „dziel i zwyciężaj” (ang. „divide and conquer”) to algorytmiczna strategia, która polega na podziale złożonego problemu na mniejsze, dające się lepiej zarządzać części. Podproblemy rozwiązywane są niezależnie, a następnie łączymy wyniki, aby uzyskać rozwiązanie problemu macierzystego.
Merge Sort – mechanizm działania
- Dzielenie (ang. Divide) – W pierwszym kroku tablicę dzieli się na dwie równe części, tj. lewą i prawą część. Środkowy indeks tablicy jest obliczany jako (lewy + prawy) / 2, gdzie „lewy” to indeks początku, a „prawy” to indeks końca tablicy.
- Sortowanie (ang. Conquer) – Następnie rekurencyjnie sortuje się obie części tablicy, tj. lewą i prawą, aż do momentu, gdy pozostają pojedyncze elementy. Sortowanie to jest wykonywane w sposób rekurencyjny.
- Scalanie (ang. Merge): Po uzyskaniu pojedynczych elementów w wyniku sortowania, scalane są one w jedną posortowaną tablicę. W tym kroku porównuje się elementy z lewej i prawej strony i umieszcza się je w odpowiedniej kolejności w wynikowej tablicy.
Algorytm Merge Sort jest stabilny, co oznacza, że nie zmienia kolejności równych elementów w wyniku sortowania. Jest to również algorytm „out-of-place”, co oznacza, że tworzy nową tablicę na posortowane dane, nie nadpisując oryginalnej tablicy.
➡ ZOBACZ 👉: Java | Biblioteka Arrays
➡ ZOBACZ 👉: Rekurencja ➿ rekursja ➿ rekurencja
Merge Sort – Algorytm
public static void mergeSort(int[] array) { if (array.length <= 1) { return; } int middle = array.length / 2; int[] left = new int[middle]; int[] right = new int[array.length - middle]; for (int i = 0; i < middle; i++) { left[i] = array[i]; } for (int i = middle; i < array.length; i++) { right[i - middle] = array[i]; } mergeSort(left); mergeSort(right); merge(array, left, right); }
Metoda przyjmuje jako argument tablicę liczb całkowitych. Obliczamy środek tablicy. Tworzymy dwie tablice, lewą, do której kopiujemy elementy od początku tablicy do środka i prawą, od środka do końca. Następnie wywołujemy rekurencyjnie mergeSort() dla lewej i prawej podtablicy.
➡ ZOBACZ 👉: Kurs Java | Darmowy Kurs Programowania w Javie
Na koniec wywołujemy metodę merge() która sortuje elementy i scala je do nowej tablicy.
private static void merge(int[] array, int[] left, int[] right) { int i = 0, j = 0, k = 0; while (i < left.length && j < right.length) { if (left[i] < right[j]) { array[k++] = left[i++]; } else { array[k++] = right[j++]; } } while (i < left.length) { array[k++] = left[i++]; } while (j < right.length) { array[k++] = right[j++]; } }
Java – Merge Sort – podsumowanie
Merge Sort jest algorytmem sortowania, który ma szerokie zastosowanie w różnych dziedzinach programowania i informatyki. Jego efektywność i stabilność czynią go atrakcyjnym wyborem w przypadku sortowania danych. W praktyce jest wykorzystywany w sortowaniu list obiektów, operacjach na grafach, systemach baz danych oraz we wbudowanych funkcjach sortujących wielu języków programowania i frameworków. Dzięki temu zrozumienie Merge Sort jest wartościowym aktywem dla każdego programisty.
➡ ZOBACZ 👉: Java | Sortowanie przez wybieranie
➡ ZOBACZ 👉: Java | Sortowanie szybkie – Quick Sort
➡ ZOBACZ 👉: Java | Sortowanie bąbelkowe – Bubble Sort
20+ BONUSOWYCH materiałów z programowania
e-book – „8 rzeczy, które musisz wiedzieć, żeby dostać pracę jako programista”,
e-book – „Java Cheat Sheet”,
checklista – „Pytania rekrutacyjne”
i wiele, wiele wiecej!