Merge Sort – Sortowanie przez Scalanie, Merge Sort

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.

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

1. 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.
2. 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.
3. 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