jario_
Zur Übersicht

Algorithmen und Datenstrukturen · Kapitel 2

Einfache Sortierverfahren

Die binäre Suche aus dem letzten Kapitel braucht ein sortiertes Array. Aber wie wird ein Array sortiert? In diesem Kapitel lernst du die drei klassischen einfachen Verfahren kennen: Bubble Sort, Selection Sort und Insertion Sort. Sie sind nicht die schnellsten, aber leicht zu verstehen, und sie kommen in fast jeder Prüfung vor.

Bubble Sort

Alle drei Verfahren sortieren in place: Sie arbeiten direkt im übergebenen Array und brauchen außer ein paar Variablen keinen weiteren Speicher. Ihr Grundbaustein ist das Vertauschen zweier Elemente mit einer Hilfsvariable.

Bubble Sort geht in Durchläufen von links nach rechts und vergleicht immer zwei Nachbarn. Ist das linke Element größer, werden sie getauscht. Nach dem ersten Durchlauf steht das größte Element ganz rechts, nach dem zweiten das zweitgrößte davor und so weiter. Der Durchlauf i muss deshalb nur noch bis a.length - 1 - i vergleichen.

Früher Abbruch: Gab es in einem Durchlauf keinen einzigen Tausch, ist das Array sortiert, und die Schleife endet mit break.

import java.util.Arrays;
public class Main {    public static void bubbleSort(int[] a) {        for (int i = 0; i < a.length - 1; i++) {            boolean swapped = false;            for (int j = 0; j < a.length - 1 - i; j++) {                if (a[j] > a[j + 1]) {                    int tmp = a[j];                    a[j] = a[j + 1];                    a[j + 1] = tmp;                    swapped = true;                }            }            System.out.println("Pass " + (i + 1) + ": " + Arrays.toString(a));            if (!swapped) {                break;            }        }    }
    public static void main(String[] args) {        int[] a = {6, 2, 9, 1, 5};        bubbleSort(a);    }}

Selection Sort

Selection Sort (Sortieren durch Auswählen) sucht im unsortierten Rest den Index des kleinsten Elements und tauscht es an die vorderste freie Position. Links wächst so ein sortierter Bereich, Schritt für Schritt um ein Element.

Pro Schritt gibt es höchstens einen Tausch, insgesamt also nur n - 1. Dafür vergleicht Selection Sort immer gleich viel, auch wenn das Array schon sortiert ist: Ob ein Element das kleinste ist, weiß es erst, wenn es den ganzen Rest angesehen hat.

import java.util.Arrays;
public class Main {    public static void selectionSort(int[] a) {        for (int i = 0; i < a.length - 1; i++) {            int min = i;            for (int j = i + 1; j < a.length; j++) {                if (a[j] < a[min]) {                    min = j;                }            }            int tmp = a[i];            a[i] = a[min];            a[min] = tmp;            System.out.println("Step " + (i + 1) + ": " + Arrays.toString(a));        }    }
    public static void main(String[] args) {        int[] a = {6, 2, 9, 1, 5};        selectionSort(a);    }}

Insertion Sort

Insertion Sort (Sortieren durch Einfügen) arbeitet wie beim Kartenspielen: Links liegt ein sortierter Bereich. Das nächste Element merkst du dir in key. Alle größeren Elemente im sortierten Bereich rücken eine Position nach rechts, und key kommt in die Lücke.

Dabei wird verschoben, nicht getauscht. Die Bedingung j >= 0 && a[j] > key muss genau in dieser Reihenfolge stehen: Ist j schon -1, verhindert &&, dass a[-1] gelesen wird.

Ist das Array fast sortiert, muss kaum etwas verschoben werden. Dann ist Insertion Sort sehr schnell.

import java.util.Arrays;
public class Main {    public static void insertionSort(int[] a) {        for (int i = 1; i < a.length; i++) {            int key = a[i];            int j = i - 1;            while (j >= 0 && a[j] > key) {                a[j + 1] = a[j];                j--;            }            a[j + 1] = key;            System.out.println("Insert " + key + ": " + Arrays.toString(a));        }    }
    public static void main(String[] args) {        int[] a = {6, 2, 9, 1, 5};        insertionSort(a);    }}

Laufzeit und Stabilität

Für ein Array mit n Elementen macht Bubble Sort im schlechtesten Fall (n - 1) + (n - 2) + … + 1 = n · (n - 1) / 2 Vergleiche. Das wächst mit n²: Bei doppelt so vielen Elementen dauert es etwa viermal so lange. Man schreibt O(n²).

  • Bubble Sort (mit Abbruch): bester Fall O(n), wenn schon sortiert, schlechtester Fall O(n²), stabil.
  • Selection Sort: immer O(n²) Vergleiche, auch im besten Fall, nicht stabil.
  • Insertion Sort: bester Fall O(n), wenn schon sortiert, schlechtester Fall O(n²), wenn umgekehrt sortiert, stabil.

Stabil heißt: Elemente mit gleichem Schlüssel behalten ihre Reihenfolge. Das ist wichtig, wenn du Objekte nach einem Attribut sortierst, etwa eine Rangliste nach Punkten. Bubble Sort und Insertion Sort tauschen oder verschieben nur, wenn ein Element echt größer ist. Selection Sort ist nicht stabil, weil der Tausch ein Element weit nach hinten werfen kann, an Gleichen vorbei.

import java.util.Arrays;
public class Main {    record Card(String suit, int rank) {}
    // Stable: equal ranks keep their order.    public static void insertionSort(Card[] cards) {        for (int i = 1; i < cards.length; i++) {            Card key = cards[i];            int j = i - 1;            while (j >= 0 && cards[j].rank() > key.rank()) {                cards[j + 1] = cards[j];                j--;            }            cards[j + 1] = key;        }    }
    // Not stable: the swap can jump over equal ranks.    public static void selectionSort(Card[] cards) {        for (int i = 0; i < cards.length - 1; i++) {            int min = i;            for (int j = i + 1; j < cards.length; j++) {                if (cards[j].rank() < cards[min].rank()) {                    min = j;                }            }            Card tmp = cards[i];            cards[i] = cards[min];            cards[min] = tmp;        }    }
    public static void main(String[] args) {        Card[] cards = {            new Card("hearts", 5), new Card("spades", 5), new Card("clubs", 2)        };        Card[] a = cards.clone();        insertionSort(a);        System.out.println("Insertion: " + Arrays.toString(a));        Card[] b = cards.clone();        selectionSort(b);        System.out.println("Selection: " + Arrays.toString(b));    }}

Zwei Karten mit Rang 5: Insertion Sort lässt Herz vor Pik, Selection Sort vertauscht sie.

Typische Fehler

  • Innere Schleife einen Schritt zu weit

    Wer a[j] mit a[j + 1] vergleicht, darf j nur bis j < a.length - 1 - i laufen lassen. Mit j < a.length - i greift der erste Durchlauf auf a[a.length] zu, und es gibt eine ArrayIndexOutOfBoundsException. Umgekehrt bleibt bei einer zu kleinen Grenze das letzte Paar unverglichen, und das Ergebnis ist falsch sortiert, ohne Fehlermeldung.

  • Wert statt Index gemerkt

    Bei Selection Sort muss min der Index des kleinsten Elements sein, nicht sein Wert. Mit nur dem Wert weißt du am Ende nicht, mit welcher Position du tauschen sollst:

    int min = a[i];   // wrong: valueint min = i;      // right: index, compare a[j] < a[min]

  • Mit >= die Stabilität verloren

    Schiebt Insertion Sort mit a[j] >= key statt a[j] > key, ist das Array zwar sortiert, aber gleiche Elemente überholen sich. Bei Zahlen merkt man das nicht, bei einer Rangliste mit gleichen Punkten schon. Dasselbe gilt für Bubble Sort: Getauscht wird nur bei >.