Sortowanie przez scalanie i quicksort w Javie

Dziel i zwyciężaj (divide and conquer) rozkłada problem na mniejsze podproblemy tego samego rodzaju, rozwiązuje je rekurencyjnie i składa rozwiązania w całość. Sortowanie przez scalanie robi to tak:

1. Warunek zakończenia: Tablica z 0 lub 1 elementem jest już posortowana.
2. Dziel: Podziel tablicę w środku (length / 2) na dwie połowy.
3. Zwyciężaj: Posortuj obie połowy rekurencyjnie.
4. Połącz: Scal (merge) dwie posortowane połowy.

Przy scalaniu dwa wskaźniki pokazują na początek obu połówek. Mniejszy element trafia do wyniku i tylko jego wskaźnik przesuwa się dalej. Gdy jedna połowa jest pusta, resztę drugiej dopisuje się na końcu.

Złożoność: Tablica jest dzielona na pół log₂ n razy, a na każdym poziomie każdy element jest łącznie scalany raz. Daje to O(n log n), zawsze, także w najgorszym przypadku. Cena: sortowanie przez scalanie potrzebuje O(n) dodatkowej pamięci na tablice pomocnicze.

1import java.util.Arrays;2
3public class Main {4    public static int[] mergeSort(int[] values) {5        if (values.length <= 1) {6            return values;7        }8        int mid = values.length / 2;9        int[] left = mergeSort(Arrays.copyOfRange(values, 0, mid));10        int[] right = mergeSort(Arrays.copyOfRange(values, mid, values.length));11        return merge(left, right);12    }13
14    public static int[] merge(int[] a, int[] b) {15        int[] result = new int[a.length + b.length];16        int i = 0;17        int j = 0;18        int k = 0;19        while (i < a.length && j < b.length) {20            if (a[i] <= b[j]) {21                result[k++] = a[i++];22            } else {23                result[k++] = b[j++];24            }25        }26        while (i < a.length) {27            result[k++] = a[i++];28        }29        while (j < b.length) {30            result[k++] = b[j++];31        }32        return result;33    }34
35    public static void main(String[] args) {36        int[] values = {38, 27, 43, 3, 9, 82, 10};37        System.out.println(Arrays.toString(mergeSort(values)));38        System.out.println(Arrays.toString(merge(new int[]{1, 4, 9}, new int[]{2, 3, 10})));39    }40}

Quicksort dzieli inaczej: wybiera element osiowy (pivot) i dzieli tablicę tak, że wszystko, co mniejsze, stoi po jego lewej stronie, a cała reszta po prawej. Potem pivot stoi na swoim ostatecznym miejscu p. Rekurencyjnie sortuje się już tylko obszary na lewo i na prawo od niego. Łączenie nie jest potrzebne, a quicksort działa w miejscu, bez tablicy pomocniczej.

W podziale Lomuto pivotem jest ostatni element a[high]. Indeks i oznacza, gdzie trafi następny mniejszy element. Drugi indeks j biegnie od low do high - 1. Jeśli a[j] < pivot, a[i] i a[j] zamieniają się miejscami, a i przesuwa się dalej. Na końcu pivot zamienia się z a[i].

Złożoność: Jeśli pivot dzieli przedział mniej więcej w środku, daje to, tak jak przy sortowaniu przez scalanie, O(n log n) i to jest przypadek średni. Jeśli jednak pivot jest zawsze najmniejszym lub największym elementem, przedział zmniejsza się tylko o jeden: O(n²) w najgorszym przypadku. Przy Lomuto dzieje się tak akurat dla tablicy już posortowanej. Dlatego w praktyce pivot wybiera się często losowo albo jako medianę z trzech elementów.

1import java.util.Arrays;2
3public class Main {4    public static void quickSort(int[] a, int low, int high) {5        if (low >= high) {6            return;7        }8        int p = partition(a, low, high);9        quickSort(a, low, p - 1);10        quickSort(a, p + 1, high);11    }12
13    // Lomuto: the last element is the pivot14    public static int partition(int[] a, int low, int high) {15        int pivot = a[high];16        int i = low;17        for (int j = low; j < high; j++) {18            if (a[j] < pivot) {19                swap(a, i, j);20                i++;21            }22        }23        swap(a, i, high);24        return i;25    }26
27    public static void swap(int[] a, int i, int j) {28        int tmp = a[i];29        a[i] = a[j];30        a[j] = tmp;31    }32
33    public static void main(String[] args) {34        int[] a = {7, 2, 9, 4, 5};35        int p = partition(a, 0, a.length - 1);36        System.out.println("pivot at " + p + ": " + Arrays.toString(a));37
38        int[] b = {38, 27, 43, 3, 9, 82, 10};39        quickSort(b, 0, b.length - 1);40        System.out.println(Arrays.toString(b));41    }42}

Algorytm oparty na porównaniach nigdy nie może być szybszy niż O(n log n). Sortowanie przez zliczanie omija tę granicę, bo w ogóle nie porównuje. Działa jednak tylko dla małych, nieujemnych liczb całkowitych, na przykład oczek na kostce, ocen albo punktów:

1. Utwórz tablicę liczników count o długości max + 1.
2. Dla każdej wartości v: count[v]++.
3. Przejdź po count i zapisz każdą wartość v dokładnie count[v] razy do wyniku.

Złożoność: O(n + k), gdzie k to liczba możliwych wartości. Przy 100 rzutach kostką z 6 możliwymi wynikami to rozwiązanie nie do pobicia. Przy wartościach do miliarda tablica liczników potrzebowałaby jednak miliarda miejsc.

1import java.util.Arrays;2
3public class Main {4    public static int[] countingSort(int[] values, int max) {5        int[] count = new int[max + 1];6        for (int v : values) {7            count[v]++;8        }9        int[] result = new int[values.length];10        int k = 0;11        for (int v = 0; v <= max; v++) {12            for (int c = 0; c < count[v]; c++) {13                result[k++] = v;14            }15        }16        return result;17    }18
19    public static void main(String[] args) {20        int[] dice = {6, 1, 3, 6, 2, 1, 5, 6};21        System.out.println(Arrays.toString(countingSort(dice, 6)));22    }23}

Algorytm sortowania jest stabilny, jeśli elementy o równym kluczu zachowują swoją pierwotną kolejność. Liczy się to, gdy sortujesz według kilku kryteriów: najpierw alfabetycznie, potem stabilnie według oceny, a przy tej samej ocenie kolejność alfabetyczna zostaje zachowana.

Sortowanie przez scalanie jest stabilne, jeśli merge przy remisie bierze element z lewej połowy, czyli porównuje przez <=. Z < stabilność ginie. Quicksort nie jest stabilny, bo zamiany rozrzucają równe elementy daleko od siebie.

• Sortowanie przez scalanie: zawsze O(n log n), O(n) dodatkowej pamięci, stabilne.
• Quicksort: średnio O(n log n), w najgorszym przypadku O(n²), w miejscu, niestabilny.
• Sortowanie przez zliczanie: O(n + k), O(k) dodatkowej pamięci na liczniki, tylko dla małych liczb całkowitych.

Java korzysta z obu: Arrays.sort dla int[] to potomek quicksorta, a dla obiektów i List.sort z kolekcji Javy to stabilny algorytm pokrewny sortowaniu przez scalanie.

1import java.util.ArrayList;2import java.util.List;3
4public class Main {5    record Order(String id, int priority) {}6
7    public static List<Order> sortByPriority(List<Order> orders) {8        if (orders.size() <= 1) {9            return new ArrayList<>(orders);10        }11        int mid = orders.size() / 2;12        List<Order> left = sortByPriority(orders.subList(0, mid));13        List<Order> right = sortByPriority(orders.subList(mid, orders.size()));14        List<Order> result = new ArrayList<>();15        int i = 0;16        int j = 0;17        while (i < left.size() && j < right.size()) {18            // <= keeps equal keys in their order: stable19            if (left.get(i).priority() <= right.get(j).priority()) {20                result.add(left.get(i++));21            } else {22                result.add(right.get(j++));23            }24        }25        while (i < left.size()) {26            result.add(left.get(i++));27        }28        while (j < right.size()) {29            result.add(right.get(j++));30        }31        return result;32    }33
34    public static void main(String[] args) {35        List<Order> orders = List.of(36            new Order("A", 2), new Order("B", 1), new Order("C", 2),37            new Order("D", 1), new Order("E", 2));38        for (Order o : sortByPriority(orders)) {39            System.out.println(o.priority() + " " + o.id());40        }41    }42}