Insertionsort

Es gibt viele verschiedene Methoden zu sortieren. Wenn der Selektionsort durchgeführt wird, wird der Subarray am Anfang des Arrays sortiert, aber der Subarray am Ende nicht. Der Selectionssort durchsucht den unsortierten Subarray nach dem nächsten Element, der in den sortierten Array verschoben werden soll.

Hier ist eine andere Möglichkeit, sich die Sortierung vorzustellen. Angenommen, Du spielst ein Kartenspiel. Du hältst die Karten in deiner Hand, und diese Karten sind sortiert. Der Geber gibt dir genau eine neue Karte. Du musst sie an der richtigen Stelle einfügen, damit die Karten, die du hältst, sortiert bleiben. Bei Selektionsort ist jedes Element, das du dem sortierten Subarray hinzufügen, nicht kleiner als die Elemente, die sich bereits im sortierten Subarray befinden. Aber in unserem Kartenbeispiel könnte die neue Karte kleiner sein als einige der Karten, die du bereits hältst, und so gehst du die Reihe entlang und vergleicht die neue Karte mit jeder Karte in deiner Hand, bis du den richtigen Platz gefunden hast. Du steckst die neue Karte an die richtige Stelle, und deine Hand hält weiterhin sortierte Karten. Dann gibt dir der Geber eine weitere Karte, und du wiederholst das gleiche Verfahren. Dann noch eine andere Karte und eine andere Karte, und so weiter, bis der Geber aufhört, dir Karten zu geben.

Das ist das Konzept von Insertionsort (auch Einfügesortieren). Beginnend mit dem Index 1 prüft man den Inhalt des Arrays. An jeder Position wird der Wert der Karte mit den bereits einsortierten Werten verglichen und an die korrekte Stelle des Subarrays eingefügt, also links von der aktuellen Position. Die nachfolgende Animation veranschaulicht den Prozess.

Stelle dir vor, dass das Subarray von Index 0 bis Index $5$‍ bereits sortiert ist. Wir wollen nun das Element von Index 6 in dieses sortierte Subarray so einfügen, dass das Subarray von Index 0 bis Index 6 sortiert ist. Wir fangen also an:

Und so soll das Subarray aussehen, wenn wir fertig sind.

Um das Element von Position 6 in das Subarray einzusortieren, vergleichen wir es immer wieder mit Elementen, die links von ihm liegen, also bewegen wir uns schrittweise von rechts nach links. Wir nennen das Element an Position 6 den key (Schlüssel). Jedes Mal, wenn wir feststellen, dass der Schlüssel kleiner ist als das Element zu seiner Linken, schieben wir dieses Element eine Position nach rechts, da wir wissen, dass der Schlüssel links zu diesem Element liegen muss (weil er ja kleiner ist). Wir müssen zwei Dinge tun, um diese Idee zu verwirklichen: Wir benötigen eine slide Operation, die ein Element um eine Position nach rechts schiebt, und wir müssen den Wert des Schlüssels an einem separaten Ort speichern (so dass er nicht durch das Element zu seiner unmittelbaren Linken überschrieben wird). In unserem Beispiel speichern wir das Element an Index 6 in einer Variable namens key:

Jetzt vergleichen wir key mit dem Element an Position 5 . Wir stellen fest, dass key (mit dem Wert 5) kleiner ist als das Element an Position 5 (Wert 13), und so schieben wir dieses Element auf Position 6:

Beachte, dass die slide Operation das Element lediglich nach rechts kopiert. Als nächstes vergleichen wir key mit dem Element an Position 4 . Wir stellen fest, dass key (Wert 5) kleiner ist als das Element an Position 4 (Wert 10), und deshalb schieben wir dieses Element an den Index 4:

Als nächstes vergleichen wir key mit dem Element an Position 3 (Wert 8). Wieder ist key kleiner als 8 und deswegen führen wir erneut eine slide Operation aus:

Das gleiche geschieht mit dem Element an Position 2:

Wir haben das Element an Position 1 erreicht, das den Wert 3 hat. Dieses Wert ist kleiner als key, und deswegen wird slide nicht ausgeführt. Stattdessen kopieren wir key an in die Position unmittelbar rechts von diesem Element (d.h. an die Position 2). Wir erinnern uns, dass dessen Element zuletzt nach rechts geschoben wurde. Im Ergebnis ist das Subarray von Index 0 bis Index 6 sortiert:

Insertionsort fügt wiederholt ein Element links in das sortierte Subarray ein. Anfänglich ist das Subarray, das nur Index 0 enthält, sortiert, da es nur ein Element enthält und ein einzelnes Element ist immer in Bezug auf sich selbst sortiert! Schauen wir uns das anhand eines Beispiels genauer an. Hier ist unser erstes Array:

Wir fangen mit dem Subarray, bestehen aus Index 0, an. Daher ist der erste Schlüssel im Index 1 . (Wir zeigen das sortierte Subarray in Rot, den Schlüssel in Gelb und den Teil des Arrays, den wir noch zu bearbeiten haben in Blau) Wir setzen den Schlüssel in das Subarray links ein:

Nun umfasst das sortierte Subarray Index 0 bis Index 1. Der neue Schlüssel befindet sich im Index 2 . Wir fügen ihn in das sortierte Subarray links ein:

Wir fahren fort, indem wir jedes weitere Element des Arrays als Schlüssel betrachten und es in das sortierte Subarray zu seiner linken einfügen:

Das gesamte Array ist sortiert sobald wir das ganz rechts stehende Element in das Array eingefügt haben.

Zwei Fälle aus unserem Beispiel sind es Wert genauer betrachtet zu werden: Erstens, wenn der einzufügende Schlüssel kleiner ist als alle Elemente zu seiner Linken (also wie wenn die Schlüssel mit den Werten 2 und 3 eingefügt werden) und zweitens, wenn er größer oder gleich allen links stehenden Elementen ist (wie wenn der Schlüssel mit dem Wert 13 eingefügt wird). Im ersten Fall gleitet jedes Element im Subarray links vom Schlüssel eine Position nach rechts und wir müssen spätestens dann aufhören, wenn wir das linke Ende des Arrays erreicht haben. Im zweiten Fall, wenn wir das erste Mal den Schlüssel mit einem links vom Schlüssel stehenden Element vergleichen, stellen wir fest, dass der Schlüssel bereits in seiner korrekten Position relativ zu allen Elementen zu seiner Linken ist. Keine Elemente wird verschoben und der Schlüssel fällt wieder in seine ursprüngliche Position zurück.

Der Hauptschritt bei Insertionsort besteht darin in einem Array Platz zu schaffen, um den aktuellen Wert der Variablen key im Array zu speichern. Wie wir bereits gesehen haben, bewegen wir uns von rechts nach links durch das Subarray, beginnend mit dem Element das links von der Ausgangsposition von key steht. Wir verschieben jedes Element, das größer als key ist eine Position nach rechts. Sobald wir ein Element gefunden haben, das kleiner als key oder gleich key ist, halten wir an und kopieren key in die freie Position direkt rechts dieses Elements. (Natürlich ist die Position nicht wirklich frei, aber ihr Element wurde vorher schon nach rechts geschoben.) Das folgende Diagramm illustriert diesen Zusammenhang:

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.