Insertionsort

Insertionsort ist die Art, wie die meisten Menschen Spielkarten auf der Hand sortieren: die nächste Karte aufnehmen und an die richtige Stelle zwischen die schon geordneten Karten schieben. Bei langen zufälligen Listen ist das Verfahren langsam, bei kurzen oder fast sortierten aber sehr schnell. Deshalb nutzen echte Sortierbibliotheken es bis heute.

Balken beim Sortieren: links ein sortierter Teil, in den ein Balken an den größeren Balken vorbei zurückrutscht
Balken beim Sortieren: links ein sortierter Teil, in den ein Balken an den größeren Balken vorbei zurückrutscht

Die Idee

Halten Sie den Anfang der Liste sortiert. Zu Beginn ist dieser sortierte Teil nur der erste Wert. Nehmen Sie den nächsten Wert und vergleichen Sie ihn mit dem Wert davor. Ist dieser größer, tauschen Sie beide und vergleichen erneut, einen Platz weiter vorn. Hören Sie auf, wenn der Wert davor nicht größer ist oder der Wert vorn angekommen ist. Der sortierte Teil ist um einen Wert gewachsen. Wiederholen Sie das mit jedem Wert bis zum Ende.

Ein Beispiel

Nehmen Sie 5, 1, 4, 2, 8. Durchlauf 1 nimmt die 1: 5 ist größer, also werden sie getauscht, und die 1 erreicht den Anfang: 1, 5, 4, 2, 8. Durchlauf 2 nimmt die 4: Sie wird mit der 5 getauscht und stoppt dann bei der 1: 1, 4, 5, 2, 8. Durchlauf 3 nimmt die 2: Sie wird mit der 5 und der 4 getauscht und stoppt dann bei der 1: 1, 2, 4, 5, 8. Durchlauf 4 nimmt die 8, die schon größer als 5 ist, also reicht ein Vergleich. Das sind 7 Vergleiche und 4 Vertauschungen. Bubblesort braucht für dieselbe Liste 9 Vergleiche, Selectionsort 10.

Vertauschungen gleich Inversionen

Eine Inversion ist ein Paar von Werten in falscher Reihenfolge. Das Tauschen zweier Nachbarn in falscher Reihenfolge beseitigt genau eine Inversion, und Insertionsort tauscht immer nur solche Nachbarn. Es macht also genau so viele Vertauschungen, wie die Startliste Inversionen hat, genauso viele wie Bubblesort. Außerdem macht jeder Durchlauf höchstens einen Vergleich, der zu keiner Vertauschung führt: den, der ihn beendet. Die Vergleiche sind also die Inversionen plus höchstens n − 1.

Adaptiv: schnell bei fast sortierten Listen

Da der Aufwand der Zahl der Inversionen plus etwa n entspricht, ist Insertionsort schnell, sobald es wenige Inversionen gibt. Eine sortierte Liste braucht n − 1 Vergleiche und keine Vertauschung. Eine Liste, in der jeder Wert nur wenige Plätze von seinem Ziel entfernt ist, braucht eine Zeit nahe n. Nur eine Liste, die weit von sortiert entfernt ist, etwa eine umgekehrte mit n(n − 1)/2 Inversionen, braucht eine Zeit proportional zu n². Bei einer zufälligen Liste sind es im Mittel etwa n²/4 Vertauschungen.

Wo es eingesetzt wird

Insertionsort ist stabil, braucht keinen zusätzlichen Speicher und hat sehr wenig Overhead. Bei kurzen Listen schlägt es Algorithmen, die auf dem Papier schneller sind. Viele Bibliothekssortierungen, etwa Timsort in Python und Java und der in C++ verwendete introsort, wechseln für kleine Teile der Liste zu Insertionsort, meist bis zu einigen Dutzend Werten. Es eignet sich auch für Daten, die Wert für Wert eintreffen, denn jeder neue Wert kann sofort eingefügt werden.

Selbst ausprobieren

Öffnen Sie die App und drücken Sie „Abspielen“, oder drücken Sie „Schritt“, um einen Vergleich nach dem anderen durchzugehen. Der Wert, der gerade eingefügt wird, hat eine eigene Farbe, der Wert, mit dem er verglichen wird, ist hervorgehoben, und der sortierte Teil ist grün. Anders als bei Bubblesort und Selectionsort ist der grüne Teil nicht endgültig: Ein späterer, kleinerer Wert kann noch hineinrutschen. Probieren Sie eine fast sortierte Liste, um zu sehen, wie kurz die Durchläufe sind, und dann eine umgekehrte.

Häufig gestellte Fragen

Welche Zeitkomplexität hat Insertionsort?

O(n²) im schlimmsten und im durchschnittlichen Fall und O(n) im besten Fall, einer bereits sortierten Liste. Genauer: Die Laufzeit ist proportional zu n plus der Zahl der Inversionen. Zusätzlicher Speicher wird nur O(1) benötigt.

Was ist der Unterschied zwischen Insertionsort und Selectionsort?

Selectionsort durchsucht den ganzen unsortierten Teil nach dem kleinsten Wert. Es macht daher immer n(n − 1)/2 Vergleiche, aber wenige Vertauschungen. Insertionsort nimmt den nächsten Wert, wie er kommt, und schiebt ihn nur so weit zurück wie nötig. Es macht daher weniger Vergleiche, besonders bei fast sortierten Listen, aber mehr Vertauschungen.

Was ist binäres Sortieren durch Einfügen?

Eine Variante, die per binärer Suche im sortierten Teil findet, wohin der neue Wert gehört. Das braucht etwa log n Vergleiche statt bis zu n. Die Werte müssen aber trotzdem verschoben werden, um Platz zu schaffen, daher bleiben die Zahl der Verschiebungen und der schlimmste Fall von O(n²) gleich.

Ist Insertionsort stabil?

Ja. Ein Wert rückt nur an echt größeren Werten vorbei zurück, daher behalten gleiche Werte ihre ursprüngliche Reihenfolge.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Insertionsort ausprobieren