MINT üben

Insertionsort

Wie sortieren Sie Spielkarten auf der Hand — und warum ist das bei fast sortierten Daten so schnell?

1

Wie Karten auf der Hand

Wer Spielkarten aufnimmt, steckt jede neue Karte sofort an die passende Stelle zwischen die schon geordneten. Genau so arbeitet Insertionsort (Insertionsort).

  • Start:das erste Element allein ist schon ein sortierter Teil.
  • Eine Runde:das erste Element des unsortierten Teils wird in einem Zwischenspeicher x gemerkt.
  • Verschieben:von rechts nach links rückt jedes Element des sortierten Teils, das größer als x ist, einen Platz nach rechts.
  • Einfügen:trifft der Vergleich auf ein Element \(\le x\) oder auf den Anfang, kommt x in die entstandene Lücke.
ixrücken nach rechtsVergleichehand danach
14914 9 | 7 2 8
27924 7 9 | 2 8
329, 7, 432 4 7 9 | 8
48922 4 7 8 9
  • Verschieben statt Tauschen:jedes größere Element wird nur einmal kopiert; x wird erst ganz am Ende geschrieben.

Ziehe die angehobene Karte mit Maus oder Finger an ihren Platz im sortierten Teil (oder verschiebe sie mit ←/→) und prüfe mit Enter. Probiere danach „Vorsortiert“ und „Umgekehrt“.

Karte einfügen

Halte fest: Eine Karte wandert nur so weit nach links, wie links von ihr größere Karten liegen — liegt sie schon richtig, kostet sie einen einzigen Vergleich.

Merke

Insertionsort (Sortieren durch Einfügen): Man steckt jedes Element an die passende Stelle des schon sortierten Teils, wie Spielkarten auf der Hand.

Start: Das erste Element allein ist ein sortierter Teil.

Eine Runde: Das erste Element des unsortierten Teils wird in einem Zwischenspeicher x gemerkt; im sortierten Teil rückt von rechts nach links jedes Element, das größer als x ist, einen Platz nach rechts.

Einfügen: Bei einem Element \(\le x\) oder am Anfang kommt x in die Lücke. Es wird nur verschoben, nicht getauscht.

2

Algorithmus und Aufwand

Die äußere Schleife holt das nächste Element, die innere while-Schleife schiebt mit dem Index j nach links.

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int x = a[i];                           // Zwischenspeicher
        int j = i - 1;
        while (j >= 0 && a[j] > x) {
            a[j + 1] = a[j];                    // größeres Element rückt nach rechts
            j--;
        }
        a[j + 1] = x;                           // in die Lücke einfügen
    }
}
  • Reihenfolge:erst j >= 0 prüfen, dann a[j] lesen — sonst droht bei j = -1 eine ArrayIndexOutOfBoundsException.
  • Bester Fall:vorsortiert — jedes Element braucht genau einen Vergleich und keine Verschiebung: \(n-1\) Vergleiche.
  • Ungünstigster Fall:umgekehrt sortiert — das Element mit Index \(i\) wandert ganz nach vorn: \(i\) Vergleiche und \(i\) Verschiebungen.
Herleitung:
\(V_{\max}(n)=1+2+\ldots+(n-1)\)
| Summanden paaren
Für \(i=1,\dots,n-1\) je \(i\) Vergleiche — dieselbe Summe wie bei Selectionsort, nur rückwärts.
\(V_{\max}(n)=\dfrac{(n-1)\cdot n}{2}\)
| umstellen
\(n-1\) Summanden mit dem Mittelwert \(\frac{n}{2}\).
\(V_{\max}(n)=\dfrac{n(n-1)}{2}\)
Ergebnis
Ebenso viele Verschiebungen; für \(n=1000\) also \(499\,500\) statt \(999\) im besten Fall.
  • Stabil:wegen a[j] > x (nicht >=) stoppt x hinter einem gleich großen Element — gleiche Werte behalten ihre Reihenfolge.
Merke

Insertionsort: vorsortiert \(n-1\) Vergleiche, umgekehrt sortiert \(\dfrac{n(n-1)}{2}\) Vergleiche — stabil.

Schleife: Außen i von 1 bis Länge − 1, innen eine while-Schleife mit j >= 0 && a[j] > x; erst j >= 0 prüfen, sonst droht eine ArrayIndexOutOfBoundsException.

Bester Fall: vorsortiert, \(n-1\) Vergleiche. Ungünstigster Fall: umgekehrt sortiert, Element i wandert ganz nach vorn.

Stabil: Wegen a[j] > x (nicht >=) bleibt die Reihenfolge gleicher Werte erhalten.

3

Allgemeine Hinweise

Zwischenspeicher zuerst

Ohne x = a[i] überschreibt die erste Verschiebung a[i] — das einzufügende Element wäre verloren.

Fast sortiert? Insertionsort!

Liegen nur wenige Elemente falsch, bleibt der Aufwand nahe bei \(n-1\) Vergleichen. Selectionsort vergleicht dagegen immer \(\frac{n(n-1)}{2}\)-mal.

Einfügen nach der Schleife

Die Zuweisung a[j + 1] = x; gehört hinter die while-Schleife. Innerhalb der Schleife würde x bei jedem Schritt geschrieben.

Videos