Insertion Sort – Algorithmus, Java-Quellcode, Zeitkomplexität

Dieser Artikel ist Teil der Serie „Sortieralgorithmen: Ultimate Guide“ und …

• beschreibt die Funktionsweise von Insertion Sort,
• zeigt eine Implementierung in Java,
• leitet die Zeitkomplexität her
• und überprüft, ob die Performance der Java-Implementierung mit dem erwarteten Laufzeitverhalten übereinstimmt.

Die Quellcodes der gesamten Artikelserie findest du in meinem GitHub-Repository.

Beispiel: Sortieren von Spielkarten

Beginnen wir mit einem Spielkartenbeispiel.

Stell dir vor, du bekommst eine Karte nach der anderen gereicht. Du nimmst die erste Karte auf die Hand. Die zweite sortierst du dann links oder rechts davon ein. Die dritte je nach Größe links, dazwischen oder rechts; und auch die folgenden Karten jeweils an der richtigen Stelle:

Hast du so schon einmal Karten sortiert?

Wenn ja, dann hast du intuitiv „Insertion Sort“ angewendet (seltener: „Insertionsort“, auf Deutsch „Einfüge-Sortieren“).

Insertion Sort Algorithmus

Kommen wir vom Kartenbeispiel zum Computeralgorithmus. Nehmen wir an, wir haben ein Array mit den Elementen [6, 2, 4, 9, 3, 7]. Dieses Array soll mit Insertion Sort aufsteigend sortiert werden.

Schritt 1

Zuerst teilen wir das Array gedanklich in einen linken, sortierten Teil und einen rechten, unsortierten Teil. Der sortierte Bereich enthält zu Beginn bereits das erste Element, da ein Array mit einem einzigen Element immer als sortiert angesehen werden kann.

Schritt 2

Dann betrachten wir das erste Element des unsortierten Bereichs und prüfen, an welcher Stelle im sortierten Bereich dieses eingefügt werden muss, indem wir es mit seinem linken Nachbarn vergleichen.

Im Beispiel ist die 2 kleiner als die 6, gehört damit also links neben die 6. Um dort Platz zu machen, schieben wir die 6 um eine Position nach rechts und setzen die 2 dann auf das freigewordene Feld. Dann schieben wir die Grenze zwischen sortiertem und unsortiertem Bereich um eine Position nach rechts:

Schritt 3

Wir betrachten wieder das erste Element des unsortierten Bereichs, die 4. Diese ist kleiner als die 6, aber nicht kleiner als die 2 und gehört somit zwischen die 2 und die 6. Wir schieben also die 6 erneut um ein Feld nach rechts und setzen die 4 auf das freigewordene Feld:

Schritt 4

Das nächste zu sortierende Element ist die 9. Diese ist größer als ihr linker Nachbar 6, und damit größer als alle Elemente des sortierten Bereichs. Sie ist also bereits an der richtigen Stelle, sodass wir in diesem Schritt kein Element verschieben müssen:

Schritt 5

Das nächste Element ist die 3. Diese ist kleiner als die 9, die 6 und die 4, aber größer als die 2. Wir schieben daher die 9, 6 und 4 um je ein Feld nach rechts und setzen dann die 3 an die Stelle, an der die 4 zuvor war:

Schritt 6

Bleibt noch die 7 – sie ist kleiner als die 9, aber größer als die 6. Also schieben wir die 9 um ein Feld nach rechts und setzen die 7 auf die freigewordene Position:

Damit ist das Array fertig sortiert.

Insertion Sort Java Quellcode

Der folgende Java-Quellcode zeigt, wie einfach man Insertion Sort implementieren kann.

Die äußere Schleife iteriert – beginnend beim zweiten Element, da das erste ja bereits als sortiert gilt – über die einzusortierenden Elemente. Die Schleifenvariable i zeigt also immer auf das erste Element des rechten, unsortierten Teils.

In der inneren while-Schleife erfolgt die Suche nach der Einfügeposition und das Verschieben der Elemente kombiniert:

• das Suchen in der Schleifenbedingung: bis das Element links von der Suchposition j kleiner ist als das einzusortierende Element,
• und das Verschieben der sortierten Elemente im Schleifenrumpf.

public class InsertionSort {
  public static void sort(int[] elements) {
    for (int i = 1; i < elements.length; i++) {
      int elementToSort = elements[i];

      // Move element to the left until it's at the right position
      int j = i;
      while (j > 0 && elementToSort < elements[j - 1]) {
        elements[j] = elements[j - 1];
        j--;
      }
      elements[j] = elementToSort;
    }
  }
}

Der abgebildete Code unterscheidet sich in zwei Punkten vom Code im GitHub-Repository: Die Klasse InsertionSort im Repository implementiert zum einen das Interface SortAlgorithm, um innerhalb meines Testframeworks einfach austauschbar zu sein.

Zum anderen erlaubt sie die Angabe von Start- und Endindex, um auch Sub-Arrays sortieren zu können. Dies wird es uns später ermöglichen, Quicksort zu optimieren, indem wir Teilarrays, die eine gewisse Größe unterschreiten, mit Insertion Sort sortieren lassen, anstatt diese weiter aufzuteilen.

Insertion Sort Zeitkomplexität

Wir bezeichnen die Anzahl der zu sortierenden Elemente mit n, im Beispiel oben wäre n = 6.

Die zwei ineinander verschachtelten Schleifen sind ein Indiz dafür, dass wir es mit quadratischem Aufwand zu tun haben, also mit einer Zeitkomplexität von O(n²). Das wäre dann der Fall, wenn sowohl die äußere als auch die innere Schleife bis zu einem Wert zählen, der linear mit der Anzahl der Elemente steigt.

Bei der äußeren Schleife ist das offensichtlich, da diese bis n zählt.

Und die innere Schleife? Diese analysieren wir in den nächsten vier Abschnitten.

Zeitkomplexität im average case

Schauen wir uns noch einmal das Beispiel von oben an, in dem wir das Array [6, 2, 4, 9, 3, 7] sortiert haben.

Im ersten Schritt des Beispiels haben wir das erste Element als bereits sortiert definiert; im Quellcode wird dieses einfach übersprungen.

Im zweiten Schritt haben wir ein Element aus dem sortierten Bereich verschoben. Wäre das einzusortierende Element bereits an der richtigen Stelle gewesen, hätten wir nichts verschieben müssen. Das heißt, dass wir im Durchschnitt im zweiten Schritt 0,5 Verschiebe-Operationen haben.

Im dritten Schritt haben wir ebenfalls ein Element verschoben. Hier hätten es aber auch null oder zwei Verschiebungen sein können. Im Durchschnitt ist es in diesem Schritt eine Verschiebung.

In Schritt vier brauchten wir keine Elemente zu verschieben. Es hätten hier aber auch ein, zwei oder drei Verschiebungen nötig sein können, im Durchschnitt sind es hier 1,5.

In Schritt fünf haben wir im Durchschnitt zwei Verschiebe-Operationen:

Und im sechsten Schritt 2,5:

In Summe haben wir also durchschnittlich 0,5 + 1 + 1,5 + 2 + 2,5 = 7,5 Verschiebe-Operationen.

Das können wir auch wie folgt ausrechnen:

Sechs Elemente mal fünf Verschiebe-Schritte; geteilt durch zwei, da im Durchschnitt über alle Schritte die Hälfte der Elemente bereits sortiert ist; und nochmal geteilt durch zwei, da das einzusortierende Element im Durchschnitt bis zur Mitte der bereits sortierten Elemente geschoben werden muss:

6 × 5 × ½ × ½   =   30 × ¼   =   7,5

Die folgende Grafik zeigt noch einmal alle Schritte:

Ersetzen wir 6 durch n, erhalten wir:

n × (n - 1) × ¼

Ausmultipliziert ergibt das:

¼ n² - ¼ n

Die höchste Potenz von n in diesem Term ist n²; die Zeitkomplexität für das Verschieben beträgt daher O(n²). Dies wird auch als „quadratischer Aufwand“ bezeichnet.

Wir haben bisher nur das Verschieben der sortierten Elemente betrachtet – doch was ist mit dem Vergleichen der Elemente und dem Setzen des zu sortierenden Elements auf das freigewordene Feld?

Vergleichsoperationen haben wir jeweils eine mehr als Verschiebe-Operationen (bzw. gleich viel, wenn bis ganz nach links geschoben wird). Die Zeitkomplexität für die Vergleichsoperationen ist damit ebenso O(n²).

Das einzusortierende Element müssen wir genauso oft an die richtige Position setzen wie es Elemente gibt abzgl. derjenigen, die sich schon an der richtigen Stelle befinden. Also maximal (n - 1)-mal. Da hier kein n² vorkommt, sondern nur ein n, sprechen wir von „linearem Aufwand“, notiert als O(n).

Bei der Betrachtung der Gesamtkomplexität zählt nur die höchste Komplexitätsstufe (s. a. „O-Notation und Zeitkomplexität – anschaulich erklärt“). Daher gilt:

Die Zeitkomplexität von Insertion Sort beträgt im average case: O(n²)

Wo es einen average case gibt, gibt es auch einen worst und einen best case.

Zeitkomplexität im worst case

Im worst case sind die Elemente zu Beginn komplett absteigend sortiert. In jedem Schritt müssen somit alle Elemente des sortierten Teil-Arrays nach rechts verschoben werden, damit das einzusortierende Element – welches in jedem Schritt kleiner ist als alle bereits sortierten Elemente – ganz an den Anfang gesetzt werden kann.

Im folgenden Diagramm wird dies dadurch demonstriert, dass die Pfeile immer nach ganz links zeigen.

Der Term aus dem average case ändert sich daher insofern, als das zweite Teilen durch zwei wegfällt:

6 × 5 × ½

Bzw.:

n × (n - 1) × ½

Wenn wir dies ausmultiplizieren, erhalten wir:

½ n² - ½ n

Auch wenn wir doppelt so viele Operationen haben wie im durchschnittlichen Fall, ändert sich an der Zeitkomplexität nichts – der Term enthält immer noch ein n², und somit gilt:

Die Zeitkomplexität von Insertion Sort beträgt im worst case: O(n²)

Zeitkomplexität im best case

Der best case wird interessant!

Wenn die Elemente bereits in sortierter Reihenfolge vorliegen, gibt es in der inneren Schleife jeweils einen Vergleich und keine Verschiebe-Operation.

Bei n Elementen, also n - 1 Schritten (da wir beim zweiten Element beginnen), kommen wir somit auf n - 1 Vergleichsoperationen.

Die Zeitkomplexität von Insertion Sort beträgt somit im best case: O(n)

Zeitkomplexität bei fast sortierten Elementen

Best und worst case sind Grenzfälle. Wie lange Insertion Sort für ein beliebiges Array braucht, lässt sich mit einer einzigen Zahl beschreiben.

Diese Zahl ist die Anzahl der sogenannten Inversionen – der Paare von Elementen, die in der falschen Reihenfolge stehen. Das fast sortierte Array [2, 4, 3, 6, 9, 7] hat genau zwei davon: (4, 3) und (9, 7).

Jede Verschiebe-Operation schiebt ein Element, das größer ist als das einzusortierende, an diesem vorbei nach rechts. Damit beseitigt sie genau eine Inversion – und keine andere Reihenfolge ändert sich.

Insertion Sort verschiebt also genauso oft, wie das Array Inversionen hat. Du siehst das an der folgenden Grafik: Nur die 3 und die 7 wandern, jeweils um eine Position.

Bezeichnen wir die Anzahl der Inversionen mit k, dann macht Insertion Sort k Verschiebungen und höchstens k + n - 1 Vergleiche. Die Zeitkomplexität beträgt also O(n + k).

Die drei Fälle von oben – best, worst und average case – sind Sonderfälle davon:

• Ein aufsteigend sortiertes Array hat keine Inversionen – das ist der best case mit O(n).
• Ein absteigend sortiertes Array hat n × (n - 1) × ½ Inversionen – genau die Verschiebungen des worst case.
• Ein zufällig angeordnetes Array hat im Durchschnitt n × (n - 1) × ¼ Inversionen – die Verschiebungen des average case.

Algorithmen, deren Laufzeit so mit der Vorsortierung sinkt, heißen adaptiv. Für Insertion Sort heißt das: Stehen nur m Elemente an der falschen Stelle, gibt es höchstens m × (n - 1) Inversionen – bei wenigen solchen Elementen bleibt der Aufwand linear.

Insertion Sort ist außerdem ein sogenannter Online-Algorithmus: Er kann die Elemente einsortieren, während sie eintreffen, ohne das Ende der Eingabe zu kennen. Genau das hast du im Kartenbeispiel vom Anfang gemacht.

Insertion Sort mit binärer Suche?

Könnten wir den Algorithmus nicht beschleunigen, indem wir die Einfügeposition mit binärer Suche suchen? Diese ist doch deutlich schneller als die sequenzielle Suche – sie hat eine Zeitkomplexität von O(log n).

Ja, das könnten wir. Allerdings hätten wir bei der Zeitkomplexität dadurch nichts gewonnen, da wir zum Verschieben trotzdem jedes Element ab der Einfügeposition um eine Position nach rechts verschieben müssten, was in einem Array eben nur schrittweise geht. Somit bliebe die innere Schleife trotz der binären Suche bei linearem Aufwand, der Gesamtalgorithmus also weiterhin bei quadratischem Aufwand, also O(n²).

Ganz umsonst wäre die binäre Suche dennoch nicht: Die Anzahl der Vergleiche sinkt damit von O(n²) auf O(n log n). Das lohnt sich, wenn Vergleiche teuer sind – etwa bei Objekten, die über einen Comparator verglichen werden. Genau deshalb sortiert TimSort, das das JDK in Arrays.sort() für Objekt-Arrays einsetzt, kurze Teilbereiche mit einem binären Insertion Sort.

Insertion Sort mit verketteter Liste?

Wenn die Elemente in einer verketteten Liste vorliegen, könnten wir dann nicht ein Element in konstanter Zeit, also O(1) einfügen?

Ja, das könnten wir. Allerdings erlaubt eine verkettete Liste keine binäre Suche. D. h. wir müssten in der inneren Schleife dennoch über alle sortierten Elemente iterieren, um die Einfügeposition zu finden. Womit wir wiederum bei linearem Aufwand für die innere Schleife wären – und damit bei quadratischem Aufwand für den Gesamtalgorithmus.

Laufzeit des Java-Insertion-Sort-Beispiels

Nach so viel Theorie wird es Zeit, diese anhand der oben vorgestellten Java-Implementierung zu überprüfen.

Das GitHub-Repository enthält das Programm UltimateTest, das Insertion Sort und alle weiteren Sortieralgorithmen dieser Artikelserie misst:

• für Array-Größen ab 1.024 Elementen, jeweils verdoppelt, bis ein Sortiervorgang länger als 20 Sekunden dauert (höchstens bis 536.870.912 Elemente);
• mit unsortierten, aufsteigend sortierten und absteigend sortierten Elementen;
• mit zwei Warm-up-Runden, damit der HotSpot-Compiler den Code optimieren kann.

Hier das Ergebnis für Insertion Sort (der Übersicht halber nur ein Auszug):

n	unsortiert	absteigend	aufsteigend
...	...	...	...
32.768	47,18 ms	94,19 ms	0,029 ms
65.536	188,32 ms	375,54 ms	0,052 ms
131.072	753,98 ms	1.492,56 ms	0,094 ms
262.144	3.005,84 ms	5.957,16 ms	0,177 ms
524.288	12.017,57 ms	23.589,69 ms	0,352 ms
1.048.576	–	–	0,696 ms
...	...	...	...
536.870.912	–	–	353,554 ms

Man kann gut sehen,

• wie sich die Laufzeit bei Verdopplung der Eingabemenge bei unsortierten und absteigend sortierten Elementen vervierfacht (Faktor 3,94 bis 4,00),
• wie die Laufzeit im worst case doppelt so groß ist wie im average case (Faktor 1,96 bis 2,00),
• wie die Laufzeit bei aufsteigend sortierten Elementen linear wächst und deutlich kleiner ist.

Das entspricht den erwarteten Zeitkomplexitäten O(n²) und O(n).

Hier die Messwerte noch einmal als Diagramm:

Bei aufsteigend vorsortierten Elementen ist Insertion Sort so schnell, dass die Kurve keinen sichtbaren Ausschlag nach oben zeigt. Hier daher die Kurve noch mal einzeln, bis 536.870.912 Elemente:

Weitere Eigenschaften von Insertion Sort

Platzkomplexität von Insertion Sort

Die Platzkomplexität von Insertion Sort ist konstant, da wir außer den Schleifenvariablen i und j sowie der Hilfsvariablen elementToSort keinen zusätzlichen Speicherplatz benötigen. D. h. egal ob wir 10 Elemente sortieren oder eine Million, wir benötigen immer nur diese drei zusätzlichen Variablen. Konstanten Aufwand notiert man als O(1).

Ist Insertion Sort stabil?

Ja. Wir verschieben nur Elemente, die größer als das einzusortierende Element sind (nicht „größer oder gleich“). Die relative Position zweier gleicher Elemente zueinander ändert sich also nie.

Lässt sich Insertion Sort parallelisieren?

Nicht direkt. Allerdings gibt es eine Verallgemeinerung von Insertion Sort, deren Teilfolgen sich parallel sortieren lassen: Shellsort.

Insertion Sort vs. Selection Sort

Insertion Sort ist in allen drei Fällen schneller als Selection Sort: bei unsortierten Elementen um rund 40 %, weil es im Durchschnitt nur halb so viele Vergleiche braucht; bei aufsteigend sortierten um Größenordnungen, weil es pro Element nur einmal vergleicht; und bei absteigend sortierten um 14 bis 17 %. Die Messwerte dazu, von derselben Maschine und demselben JDK, findest du im Artikel über Selection Sort.

Zusammenfassung

Insertion Sort ist ein sehr einfach zu implementierender, stabiler Sortieralgorithmus mit einer Zeitkomplexität von O(n²) im average und worst case, und O(n) im best case. Allgemein hängt seine Laufzeit an der Anzahl k der Inversionen: O(n + k) – bei fast sortierten Elementen ist Insertion Sort also nahezu linear.

Für sehr kleine n ist Insertion Sort schneller als effizientere Algorithmen wie Quicksort oder Mergesort, sodass diese Algorithmen kleinere Teilprobleme mit Insertion Sort lösen.

Die Dual-Pivot-Quicksort-Implementierung in Arrays.sort() des JDK für primitive Arrays etwa sortiert den Teilbereich am linken Rand mit Insertion Sort, sobald er weniger als 44 Elemente hat. Alle anderen Teilbereiche übergibt sie schon früher an eine Insertion-Sort-Variante – bei weniger als 65 Elementen plus einem Zuschlag, der mit der Rekursionstiefe wächst.

Weitere Sortieralgorithmen findest du in dieser Übersicht aller Sortieralgorithmen und ihrer Eigenschaften im ersten Teil der Artikelserie.