jario_
Wróć do przeglądu

Algorytmy i struktury danych · Rozdział 3

Schnelle Sortierverfahren

Bubble, Selection und Insertion Sort brauchen O(n²) Schritte. Bei 1 000 Elementen sind das rund eine Million Vergleiche, bei einer Million Elementen schon eine Billion. Die Verfahren in diesem Kapitel schaffen dasselbe in O(n log n), bei einer Million Elementen also in etwa 20 Millionen Schritten. Der Trick dahinter heißt Teile und herrsche.

Teile und herrsche: Merge Sort

Teile und herrsche (divide and conquer) zerlegt ein Problem in kleinere Teilprobleme derselben Art, löst sie rekursiv und setzt die Lösungen zusammen. Merge Sort macht das so:

  1. Abbruchfall: Ein Array mit 0 oder 1 Element ist schon sortiert.
  2. Teilen: Das Array in der Mitte (length / 2) in zwei Hälften teilen.
  3. Herrschen: Beide Hälften rekursiv sortieren.
  4. Zusammenfügen: Die zwei sortierten Hälften mischen (merge).

Beim Mischen zeigen zwei Zeiger auf den Anfang beider Hälften. Das kleinere Element wandert ins Ergebnis, nur sein Zeiger rückt weiter. Ist eine Hälfte leer, wird der Rest der anderen angehängt.

Laufzeit: Das Array wird log₂ n Mal halbiert, und auf jeder Ebene wird insgesamt jedes Element einmal gemischt. Das ergibt O(n log n), immer, auch im schlechtesten Fall. Der Preis: Merge Sort braucht O(n) zusätzlichen Speicher für die Hilfsarrays.

import java.util.Arrays;
public class Main {    public static int[] mergeSort(int[] values) {        if (values.length <= 1) {            return values;        }        int mid = values.length / 2;        int[] left = mergeSort(Arrays.copyOfRange(values, 0, mid));        int[] right = mergeSort(Arrays.copyOfRange(values, mid, values.length));        return merge(left, right);    }
    public static int[] merge(int[] a, int[] b) {        int[] result = new int[a.length + b.length];        int i = 0;        int j = 0;        int k = 0;        while (i < a.length && j < b.length) {            if (a[i] <= b[j]) {                result[k++] = a[i++];            } else {                result[k++] = b[j++];            }        }        while (i < a.length) {            result[k++] = a[i++];        }        while (j < b.length) {            result[k++] = b[j++];        }        return result;    }
    public static void main(String[] args) {        int[] values = {38, 27, 43, 3, 9, 82, 10};        System.out.println(Arrays.toString(mergeSort(values)));        System.out.println(Arrays.toString(merge(new int[]{1, 4, 9}, new int[]{2, 3, 10})));    }}

Quicksort

Quicksort teilt anders: Es wählt ein Pivot-Element und partitioniert das Array so, dass alles Kleinere links und alles andere rechts davon steht. Danach steht das Pivot an seiner endgültigen Stelle p. Nur noch die Bereiche links und rechts davon werden rekursiv sortiert. Zusammenfügen ist nicht nötig, und Quicksort arbeitet in place, ohne Hilfsarray.

Bei der Partition nach Lomuto ist das Pivot das letzte Element a[high]. Ein Index i markiert, wo das nächste kleinere Element hinkommt. Ein zweiter Index j läuft von low bis high - 1. Ist a[j] < pivot, werden a[i] und a[j] getauscht, und i rückt weiter. Am Ende tauscht das Pivot mit a[i].

Laufzeit: Teilt das Pivot den Bereich ungefähr in der Mitte, ergibt das wie bei Merge Sort O(n log n), und das ist der Durchschnitt. Ist das Pivot aber immer das kleinste oder größte Element, schrumpft der Bereich nur um eins: O(n²) im schlechtesten Fall. Mit Lomuto passiert das ausgerechnet bei einem schon sortierten Array. In der Praxis wählt man das Pivot deshalb oft zufällig oder als Mittelwert aus drei Elementen.

import java.util.Arrays;
public class Main {    public static void quickSort(int[] a, int low, int high) {        if (low >= high) {            return;        }        int p = partition(a, low, high);        quickSort(a, low, p - 1);        quickSort(a, p + 1, high);    }
    // Lomuto: the last element is the pivot    public static int partition(int[] a, int low, int high) {        int pivot = a[high];        int i = low;        for (int j = low; j < high; j++) {            if (a[j] < pivot) {                swap(a, i, j);                i++;            }        }        swap(a, i, high);        return i;    }
    public static void swap(int[] a, int i, int j) {        int tmp = a[i];        a[i] = a[j];        a[j] = tmp;    }
    public static void main(String[] args) {        int[] a = {7, 2, 9, 4, 5};        int p = partition(a, 0, a.length - 1);        System.out.println("pivot at " + p + ": " + Arrays.toString(a));
        int[] b = {38, 27, 43, 3, 9, 82, 10};        quickSort(b, 0, b.length - 1);        System.out.println(Arrays.toString(b));    }}

Counting Sort

Ein Vergleichsverfahren kann nie schneller als O(n log n) sein. Counting Sort umgeht diese Grenze, weil es gar nicht vergleicht. Es funktioniert aber nur für kleine, nicht negative ganze Zahlen, etwa Würfelaugen, Noten oder Punkte:

  1. Ein Zähl-Array count der Länge max + 1 anlegen.
  2. Für jeden Wert v: count[v]++.
  3. Über count laufen und jeden Wert v genau count[v]-mal ins Ergebnis schreiben.

Laufzeit: O(n + k), wobei k die Anzahl möglicher Werte ist. Bei 100 Würfen mit 6 möglichen Augen ist das unschlagbar. Bei Werten bis eine Milliarde bräuchte das Zähl-Array aber eine Milliarde Plätze.

import java.util.Arrays;
public class Main {    public static int[] countingSort(int[] values, int max) {        int[] count = new int[max + 1];        for (int v : values) {            count[v]++;        }        int[] result = new int[values.length];        int k = 0;        for (int v = 0; v <= max; v++) {            for (int c = 0; c < count[v]; c++) {                result[k++] = v;            }        }        return result;    }
    public static void main(String[] args) {        int[] dice = {6, 1, 3, 6, 2, 1, 5, 6};        System.out.println(Arrays.toString(countingSort(dice, 6)));    }}

Stabilität und Vergleich

Ein Sortierverfahren ist stabil, wenn Elemente mit gleichem Schlüssel in ihrer ursprünglichen Reihenfolge bleiben. Das zählt, wenn man nach mehreren Kriterien sortiert: Erst alphabetisch, dann stabil nach Note, und bei gleicher Note bleibt die alphabetische Reihenfolge erhalten.

Merge Sort ist stabil, wenn merge bei Gleichstand das Element aus der linken Hälfte nimmt, also mit <= vergleicht. Mit < geht die Stabilität verloren. Quicksort ist nicht stabil, weil die Tauschvorgänge gleiche Elemente über weite Strecken durcheinanderbringen.

  • Merge Sort: immer O(n log n), O(n) Extra-Speicher, stabil.
  • Quicksort: im Schnitt O(n log n), im schlechtesten Fall O(n²), in place, nicht stabil.
  • Counting Sort: O(n + k), O(k) Extra-Speicher für die Zähler, nur für kleine ganze Zahlen.

Java nutzt beides: Arrays.sort für int[] ist ein Quicksort-Abkömmling, für Objekte und List.sort ein stabiles, Merge-Sort-artiges Verfahren.

import java.util.ArrayList;import java.util.List;
public class Main {    record Order(String id, int priority) {}
    public static List<Order> sortByPriority(List<Order> orders) {        if (orders.size() <= 1) {            return new ArrayList<>(orders);        }        int mid = orders.size() / 2;        List<Order> left = sortByPriority(orders.subList(0, mid));        List<Order> right = sortByPriority(orders.subList(mid, orders.size()));        List<Order> result = new ArrayList<>();        int i = 0;        int j = 0;        while (i < left.size() && j < right.size()) {            // <= keeps equal keys in their order: stable            if (left.get(i).priority() <= right.get(j).priority()) {                result.add(left.get(i++));            } else {                result.add(right.get(j++));            }        }        while (i < left.size()) {            result.add(left.get(i++));        }        while (j < right.size()) {            result.add(right.get(j++));        }        return result;    }
    public static void main(String[] args) {        List<Order> orders = List.of(            new Order("A", 2), new Order("B", 1), new Order("C", 2),            new Order("D", 1), new Order("E", 2));        for (Order o : sortByPriority(orders)) {            System.out.println(o.priority() + " " + o.id());        }    }}

Typowe błędy

  • Rest beim Mischen vergessen

    Die Hauptschleife von merge endet, sobald eine Hälfte leer ist. Fehlen danach die Schleifen, die den Rest der anderen Hälfte kopieren, bleiben am Ende des Ergebnisses Nullen stehen. Es braucht beide: eine für den Rest links und eine für den Rest rechts.

  • Falsche Grenzen bei der Rekursion

    Bei Quicksort gehört das Pivot an Stelle p zu keinem Teil mehr. Rekursiert man mit quickSort(a, low, p) statt p - 1, kann derselbe Bereich immer wieder kommen, bis ein StackOverflowError folgt. Bei Merge Sort mit Grenzen im selben Array (left..mid, mid+1..right) passiert dasselbe, wenn mid doppelt oder gar nicht vorkommt.

  • Stabilität mit < verspielt

    In merge sieht if (a[i] < b[j]) harmlos aus. Bei Gleichstand nimmt es aber das Element aus der rechten Hälfte zuerst, obwohl es ursprünglich weiter hinten stand. Das Ergebnis ist noch sortiert, aber nicht mehr stabil. Richtig ist <=.