Insertion Sort

Insertion Sort Erklärung

Der Insertion Sort gehört in der Informatik zu den stabilen Sortieralgorithmen und kann als Sortieren durch Einfügen beschrieben werden, deswegen auch Einfügesortierenmethode genannt. Das Ganze lässt sich natürlich einfach durch die englischen Wörter insertion = Einfügen und sort = sortieren ableiten, weswegen der Sortieralgorithmus auch manchmal als Insertsort bezeichnet wird. Allgemein kann auch noch gesagt werden, dass der Sortieralgorithmus einfach zu implementieren ist und dabei bei kleiner oder schon teilweise vorsortierten Eingabemengen sehr effizient arbeitet. Da das Sortierverfahren keinen zusätzlichen Speicherplatz benötigt, arbeitet der Algorithmus in-place, was natürlich für seine Speicherplatzkomplexität spricht.

Prinzip: Sortieren durch Einfügen

Der Grundgedanke ist eigentlich ganz einfach, da es wahrscheinlich dem am nächsten kommt, wie du selbst die Zahlen ordnen würdest. Stell dir einfach mal ein Kartenspiel vor, welches du der Größe nach sortieren musst. In deiner Hand hast du bereits die Karte Pik 5 und Pik 9. Als nächstes ziehst du die Pik 6.

direkt ins Video springen

Diese Karte ordnest du also in der Mitte zwischen den beiden anderen ein. Genau so geht der Insertion Sort auch vor.  Er durchläuft Schritt für Schritt einen Array und entnimmt dabei aus der unsortierten Eingabefolge ein Element und setzt es dann an der entsprechend richtigen Stelle wieder ein – „Sortieren durch Einfügen“. Die restlichen Elemente des Arrays müssen dann wiederrum hinter dem neu eingefügten Wert verschoben werden.

Beispiel

Aber schauen wir uns das Ganze doch einfach mal an einem ausführlicheren Beispiel an.

Es soll dieser Array der Größe nach aufsteigend sortiert werden:

[4][7][5][3][9][1][2]

Die erste Zahl ist beim Insertion Sort immer direkt als sortierter Bereich angegeben. Die restliche Liste gilt als unsortiert. Also können wir uns direkt die 7 ansehen. Die 7 soll nun an die richtige Stelle im sortierten Bereich eingefügt werden. Die 7 ist größer als die 4 und ist somit schon richtig eingeordnet. Weiter geht es nun mit der 5. Die 5 ist kleiner als die 7 und wird somit vor der 7 eingeordnet, jedoch wird davor noch geprüft, ob sie größer als 4 ist. Das ist der Fall und somit wird sie direkt zwischen 4 und 7 eingetragen.

[4][5][7][3][9][1][2]

Weiter geht es mit der vierten Position. Die 3 ist dabei nicht nur kleiner als die 7, sondern auch kleiner als die 5 und die 4. Also wird die 3 an die erste Stelle gesetzt und die anderen Zahlen entsprechend nach rechts verschoben.

[3][4][5][7][9][1][2]

Dann geht es weiter mit der Zahl 9. Die 9 ist unter den bereits sortierten Zahlen die größte Zahl und ist entsprechend vorerst auf seiner richtigen Position. Deshalb können wir gleich weiter mit der 1 machen, die sich als kleinste Zahl herausstellt und entsprechend nach vorne auf die erste Stelle einsortiert wird.

[1][3][4][5][7][9][2]

Zum Schluss fehlt uns noch die 2. Die 2 ist kleiner als die 9 und muss entsprechend auf die richtige Stelle in der restlichen Liste eingefügt werden. Also zwischen die 1 und die 3. Am Ende sieht die sortierte Liste dann so aus:

[1][2][3][4][5][7][9]

Fertig!

Algorithmus

Doch wie lässt sich der Insertion Sort als Pseudocode darstellen?

Schauen wir uns doch dafür erstmal an, wie man den allgemeinen Algorithmus beschreiben kann.

Zuerst wird eine Liste übergeben. Gestartet wird immer mit dem ersten Element, also stellt dieser den sortierten Bereich der Liste dar und der restliche Array gilt als unsortierter Bereich. Die Bedingung ist, dass solange der unsortierte Bereich Elemente hat, soll immer das erste Element aus dem unsortierten Bereich an die richtige Stelle im sortierten Bereich eingeordnet werden.

Zum Schluss erhält man dann eine sortierte Liste.

direkt ins Video springen

Insertion Sort Pseudocode

Das also zum allgemeinen Algorithmus. Jetzt bauen wir auf diesem Wissen unseren Insertion Sort Pseudocode auf. Gegeben sei also eine Liste, wir nennen sie in diesem Fall einfach mal l. Als nächstes definieren wir den sortierten Bereich mit dem ersten Element a. Anschließend bezeichnen wir dann das erste Element im unsortierten Bereich als b. Das aktuelle b wird in unserem Zwischenspeicher tmp gespeichert, solange der unsortierte Bereich Elemente besitzt. Wir entfernen das Element aus dem sortierten Bereich und setzten es aus dem Zwischenspeicher in den sortierten Bereich ein.

Insertionsort (Liste l)
  for a in 0 -> l.length – 2
  do
      b = a + 1
      tmp = l[b]
      while b > 0 AND tmp 
          l[b] = l[b-1]
          b – –
      l[b] = tmp

Insertion Sort Struktogramm

Aufbauend auf dem Pseudocode, wird hier ein zugehöriges Struktogramm (Nassi-Schneidermann-Diagramm) illustriert:

direkt ins Video springen

Insertion Sort Java

Im Folgenden siehst du eine simulierte Insertion Sort Java-Implementierung der allgemeinen Sortierfunktion.

public class Insertion_Sort_Java {
  public static void sortieren(int[] zahlenarray)
  {
    int sortiert, unsortiert, tmp;
    for (sortiert=0; sortiert
    {
      unsortiert=sortiert+1;
      for (tmp=zahlenarray[unsortiert]; unsortiert>0 && zahlenarray[unsortiert-1]>tmp; unsortiert–)
      {
        zahlenarray[unsortiert]=zahlenarray[unsortiert-1];
      }
      zahlenarray[unsortiert]=tmp;
    }
  }
}

Insertion Sort Laufzeit

Die Insertion Sort Laufzeit ist abhängig von der Anzahl von benötigten Verschiebungen, also auch abhängig von der Anordnung von Elementen im unsortierten Bereich. Sowohl der durchschnittliche Average-Case als auch der Worst-Case haben die Komplexität O(n²). Der schlechteste Fall tritt dann ein, wenn der Algorithmus beispielsweise absteigend sortiert ist und er dann aufsteigend sortiert werden soll. Im Fall, dass die Liste bereits von Beginn an sortiert ist, ist die Komplexität linear O(n), dabei handelt es sich um den Best-Case. Dabei ist der Sortieralgorithmus sogar besser als der Quicksort , Mergesort , Heapsort , usw.

Die Insertion Sort Laufzeit nochmal als Überblick:

• Worst-Case/ Schlechtester Fall:
• Average Case/ Durchschnittliche Anzahl von Vergleichen:
• Best-Case/ Bestes Szenario:

Wenn für das Sortierverfahren die binäre Suche verwendet wird, kann man die Anzahl der Vergleiche und Verschiebungen durch Sortieroperationen im Worst-Case folgendermaßen abschätzen:

Komplexität

Im Falle, dass der Array bereits „fast sortiert“ ist, also jedes der Elemente fast am richtigen Platz ist, kann die Laufzeit auch O(n) sein. In diesem Fall und auch im Best-Case-Szenario ist der Insertion Sort ziemlich schnell. Jedoch in den anderen Fällen sehr langsam, weswegen sich das Sortierverfahren nur für kleinere Datenmengen oder für das Einfügen von weiteren Elementen in eine schon geordnete Liste eignet.

Zusätzlich kann noch gesagt werden, dass der Sortieralgorithmus bezüglich Speicherplatzkomplexität punkten kann. Da der Algorithmus mittel in-place-Verfahren arbeitet, wird kein zusätzlicher Speicherplatz benötigt.