Sortieralgorithmen verstehen! Am Beispiel von Insertion-Sort in Java.

Keylearnings:

  • Was sind Sortieralgorithmen?
  • Die Eigenschaften von Sortieralgorithmen?
  • Der Insertion-Sort Algorithmus.
  • Die Komplexität von Insertion-Sort?

Ein Griff und du hast es gefunden?

Oder.

Ein Griff und die Suche kann beginnen?

Den Unterschied macht die Ordnung!

So ist es auch wenn wir in einer Datenstruktur nach einem Datensatz suchen.

In einem sortierten Datenbestand kann eine Abfrage bedeutend schneller bearbeitet werden.

Aber wie können wir sicherstellen, dass in unserer Datenstruktur Ordnung herrscht?

Hier haben wir zwei Möglichkeiten:

  1. Wir sorgen beim Einfügen eines Datensatz dafür, dass der Datenbestand sortiert bleibt.
  2. Wir räumen unsere Datenstruktur regelmäßig auf.

Welche Methode die bessere ist, hängt davon ab, ob wir überwiegend lesend oder schreibend auf unseren Datenbestand zugreifen müssen.

Die erste Möglichkeit führt zu einem höheren Aufwand beim Einfügen eines Datensatzes.

Bei Möglichkeit zwei entsteht, durch das regelmäßige Sortieren, ein höherer Pflegeaufwand, dafür können wir aber sehr einfach Datensätze in den Datenbestand einfügen.

In diesem Artikel beschäftigen wir uns mit Möglichkeit zwei und schauen uns an, wie wir eine Datenstruktur sortieren können.

Genau DAS ist nämlich die Aufgabe von Sortieralgorithmen. Ein konkretes Beispiel für einen Sortieralgorithmus ist der Insertion Sort, den wir uns im Detail ansehen wollen.

Insertion Sort Erklärung

Was ist ein Sortieralgorithmus?

Für einen Sortieralgorithmus benötigen wir zwei Dinge.

  1. Eine Menge, die wir ordnen wollen. Hierbei ist die ungeordnete Menge die Eingabe und die geordnete Menge die Ausgabe des Algorithmus.
  2. Ein Verfahren mit dem wir die Menge effizient sortieren können.

Auch müssen wir uns überlegen was es denn überhaupt bedeutet, dass ein Element a vor einem anderen Element b liegt. In Java können wir das sehr komfortabel mit Hilfe der Comparator Schnittstelle machen.

Der Einfachheit wegen beginnen wir mit einem Array von Integer-werten, die wir aufsteigend sortieren wollen.

Sortieralgorithmen sind  gut erforscht und es wurden effiziente Verfahren entwickelt. Berühmt geworden sind insbesondere folgende Sortieralgorithmen:

  • Selection-Sort
  • Bubble-Sort
  • Insertion-Sort
  • Merge-Sort
  • Quick-Sort

Und wieder einmal haben wir die Qual der Wahl.

Anstatt uns jeden Sortieralgorithmus einzeln vorzuknöpfen, wollen wir uns die entscheidenden Merkmale am Beispiel des Insertion-Sort Algorithmus ansehen.

Eigenschaften eines Sortieralgorithmus

Was macht einen guten Sortieralgorithmus aus?

Zeit- und Speicherkomplexität!

Wie immer soll unser Algorithmus eine möglichst geringe Zeit- und Speicherkomplexität aufweisen.

Insbesondere möchten wir, dass bei steigendem Datenvolumen die Komplexität so gering wie möglich ansteigt. Diese Eigenschaft, lässt sich mit Hilfe der O Notation messen.

Leider auch wie (fast) immer sind Zeit- und Speicherkomplexität gegenläufig.

Häufig werden Hilfsdatenstrukturen verwendet, welche zwar die Speicherkomplexität erhöhen, dafür aber die Zeitkomplexität verbessern.

Um die Zeitkomplexität zu verringern müssen wir dafür sorgen, dass  so wenige Tauschoperationen wie möglich stattfinden womit wir auch gleich bei der nächsten Eigenschaft sind.

Die Anpassbarkeit!

Im Idealfall sollte eine bereits sortierte Liste schneller sortiert sein (in 0 Schritten), als eine Liste, in der das totale Chaos herrscht.

Leider fehlt vielen Sortieralgorithmen der Blick für das Ganze, sodass die Verarbeitung einer bereits sortierten Liste genauso viel Zeit in Anspruch nimmt wie die einer unsortierten Liste.

Da wir bei der O Notation immer das Worst-Case Szenario betrachten, führt die Eigenschaft der Anpassbarkeit dazu, dass Algorithmen, die in der Theorie besser sein müssten, in der Praxis eine höhere Laufzeit haben.

Ein Sortieralgorithmus, der die Eigenschaft Anpassbarkeit unterstützt ist der Insertion Sort Algorithmus, den wir uns im folgenden detailiert ansehen wollen.

Der Insertion-Sort Algorithmus

Im Insertion-Sort Algorithmus gehen wir davon aus, dass die zu ordnende Liste aus zwei Teilen besteht. Einem geordneten Teil und einem ungeordneten Teil.

Bei einer vollkommen unsortierten Liste besteht der geordnete Teil zu Beginn aus einem einzelnen Element. Eine Liste die nur aus einem einzigen Element besteht ist nämlich IMMER sortiert.

Kompliziert? Okay, ich zeigs dir!

Schauen wir uns folgendes Array an:

Insertion Sort unsortiert

Bei den ersten drei Elementen handelt es sich um eine sortierte Liste, daher beginnt der Insertion Sort Algorithmus seine Arbeit erst ab Position Vier.

Je besser die Liste sortiert ist desto weniger Schritte sind also notwendig. Hieran erkennen wir die Anpassbarkeits-Eigenschaft des Insertion Sort Algorithmus.

Ziel beim Insertion-Sort ist es den sortierten Teil der Liste schrittweise zu vergrößern.

In unserem Fall bedeutet dies, dass wir das vierte Element, also den Wert 3 an die richtige Stelle einsortieren müssen.

Dazu vergleichen wir das Element an dritter Position, also den Wert 5 mit dem Wert 3 an Position vier. Da 5 größer als 3 ist vertauschen wir die Elemente und wir erhalten.

Insertion Sort Schritt 1

Als nächstes vergleichen wir Position drei (Wert 3) mit Position zwei (Wert 4). Da 4 größer als 3 ist müssen wir die Elemente vertauschen.

Nach diesem Schritt ist der sortierte Anteil der Liste um ein Element gewachsen.

Insertion-Sort-Schritt3

Jetzt verfahren wir analog mit dem ersten Element der unsortierten Liste (Position 5). D.h. wir vergleichen Position vier und fünf miteinander und stellen fest, dass 5 größer 1 gilt und vertauschen die Elemente miteinander.

Insertion-Sort Schritt 4

Als nächstes wird Position drei und vier miteinander verglichen und wieder stellen wir fest, dass diese Elemente miteinander vertauscht werden müssen und wir erhalten.

Insertion-Sort Schritt 5

Auf diese Weise verfahren wir solange bis der Wert 1 bis ganz nach vorne gewandert ist und wir schließlich eine sortierte Liste erhalten haben.

Insertion-Schritt 6.

Insertion Sort Schritt 7

Gut! Kümmern wir uns als nächstes um die Implementierung!

Die Implementierung von Insertion-Sort

Die Implementierung des Insertion-Sort Algorithmus teilt sich in zwei Schritte auf.

Zunächst muss das erste Element der unsortierten Liste gefunden werden und anschließend durch Tauschoperationen an die richtige Position in dem sortierten Teil der Liste gebracht werden.

Das machen wir mit zwei ineinander verschachtelten Schleifen.

Die erste Schleife durchläuft das gesamte Array vom ersten bis zum letzten Element. In der zweiten Schleife durchlaufen wir den sortierten Teil der Liste rückwärts und bringen das einzusortierende Element durch Vertauschungen von Nachbarelementen an die korrekte Position.

1: public static void insertionSort(int[] liste){
2:	int temp = 0;
3:	int j = 0;
4:	for(int i = 1;i < liste.length;i++){ 
5:           j = i; 
6:           while((j>0)&&(liste[j-1]>liste[j])){
7:		temp = liste[j-1];
8:		liste[j-1] = liste[j];
9:		liste[j] = temp;
10:		j--;
11:	    }
12:	}
13:}

Wir brechen die while Schleife in Zeile 6 ab, sobald wir entweder den Anfang der Liste erreicht haben (j>0) oder das einzusortierende Element die richtige Position im sortierten Teil der Liste erreicht hat (liste[j-1]>liste[j]).

In jedem Schleifendurchlauf werden Nachbarelemente vertauscht wobei es sich bei dem rechten Element um das einzusortierende (das erste Element der unsortierten Liste) Element handelt. Um die Vertauschung durchführen zu können benötigen wir eine Hilfsvariable temp.

Dieser Vorgang wird solange wiederholt bis das einzusortierende Element an die richtige Position im sortierten Teil der Liste gewandert ist.

Im folgenden Video wiederhole ich die einzelnen Schritte, die beim Insertion-Sort Algorithmus durchgeführt werden:

Okay, machen wir einen Probelauf mit dem Array aus dem Beispiel von oben.

1: int test[] = {2,4,5,3,1,8};
2: insertionSort(test);
3: for(int i = 0;i<test.length;i++){
4:	System.out.print(test[i]+" ");
5: }

Nicht sehr spektakulär!

In Zeile Eins initialisieren wir ein Test-Array, das wir in Zeile 2 als Argument an die insertionSort Funktion übergeben.

Anschließend geben wir das sortierte Array in einer for Schleife (Zeile 3-5) aus.

Die Bildschirmausgabe sieht wie folgt aus:

1 2 3 4 5 8

Sauber! Schauen wir uns die Zeitkomplexität an.

Die Zeitkomplexität des Insertion Sort Algorithmus

Bei der O Notation betrachten wir den schlechtesten Fall.

Die for Schleife in Zeile vier durchläuft das gesamte Array, ab der zweiten Stelle. D.h. bei einem Array der Länge N finden N-1 Schleifendurchläufe statt.

In der while Schleife in Zeile 6 kommt die Anpassbarkeit des Insertion-Sort Algorithmus zum tragen. Bei einer bereits sortierten Liste wird die while Schleife Null mal durchlaufen.

Der schlechteste Fall tritt auf, wenn wir eine absteigend sortierte Liste in eine aufsteigend sortierte Liste umwandeln wollen.

Überlegen wir uns wie oft der while Schleifen-Inhalt im folgenden Beispiel ausgeführt werden muss.

Insertion Sort invers

Da es sich hierbei um ein absteigend sortiertes Array handelt, besteht die sortierte Liste am Anfang nur aus dem Element mit dem Wert 8.

Die unsortierte Liste beginnt mit dem Element, das den Wert 5 enthält, um dieses an die richtige Position in der sortierten Liste zu bringen ist eine Vertauschung notwendig, d.h. die while Schleife wird genau einmal durchlaufen.

Nach diesem Schritt hat die Liste folgende Gestalt:

Insertion Sort Algorithmus

Unser Plan ist aufgegangen und der sortierte Teil der Liste hat sich um ein Element vergrößert. Der unsortierte Teil beginnt mit dem Element, das den Wert 4 enthält. Diesmal benötigen wir zwei while Schleifendurchläufe, also auch zwei Tauschoperationen um den Wert 4 an die richtige Position in der sortierten Liste zu bringen.

Jetzt hat unser Array folgende Gestalt:

Insertion Sort Algorithmus

Und wieder ist der sortierte Teil um ein Element gewachsen. Nun muss das Element mit dem Wert 3 einsortiert werden.

Hierfür benötigen wir drei while Schleifen durchläufe. Oder mit anderen Worten drei Tauschoperationen.

Insertion Sort

Langsam aber sicher ist ein Bildungsgesetz zu erkennen. Als nächstes müssen wir den Wert 2 in die richtige Position bringen wofür wir vier Tauschoperationen benötigen.

Insertion Sort Algorithmus

Jetzt haben wir es fast geschafft. Wir müssen noch das letzte Element mit dem Wert 1 nach vorne wandern lassen. Wofür wir fünf weitere while Schleifendurchläufe benötigen.

Lass uns den Taschenrechner anschmeißen und die Gesamtanzahl der Tauschoperationen bzw. der while Schleifendurchläufe aufaddieren.

Wir erhalten:

Anzahl Tauschoperationen = 5 + 4 +3 + 2 + 1 = 15.

Um ein Array mit sechs Elementen zu sortieren, werden also im schlechtesten Fall 15 Tauschoperationen benötigt.

Mit Hilfe eines scharfen Blickes stellen wir die Vermutung auf, dass für ein Array mit n Elementen im schlechtesten Fall

Anzahl Tauschoperationen = (n-1)+(n-2)…..+2+1

gilt. Diese Vermutung kann mithilfe eines Induktionsbeweises bestätigt werden.

Mit Hilfe der Gaußformel können wir obigen Ausdruck noch vereinfachen und wir erhalten.

Anzahl Tauschoperationen = n(n-1)/2 .

Und da bei der O Notation nur der Term vom höchsten Grad zu beachten ist und außerdem Konstanten keine Rolle spielen erhalten wir O(N2).

Der Insertion-Sort Algorithmus ist also von quadratischer Komplexität.

Fazit: Auch wenn die meisten Programmiersprachen Sortieralgorithmen von Haus aus mitbringen, gehört die Kenntnis von Suchalgorithmen zur Allgemeinbildung eines Informatikers. Der Insertion-Sort ist ein klassisches Beispiel für einen Suchalgorithmus.

Ich freue mich auf deine Fragen im Kommentarbereich.

Hat dir der Artikel gefallen? Dann folge uns am besten gleich auf Facebook!

Hallo ich bin Kim und ich möchte ein großer Programmierer werden. Machst du mit?

Kommentare (20)

  • Antworte

    Super, hat mir für meine Klausur geholfen, vielen Dank!

    • Hi Florian, danke für dein Feedback. Freue mich immer wenn mein geschreibsel weiterhilft! Viele Grüße Kim

  • Antworte

    Hallo! Super anschauliche Erklärung, danke 🙂 Mich würde aber noch interessieren, wie man mathematisch, also formal, zeigt, dass der Insertion sort eine sortierte Liste erzeugt. Kannst du mir weiterhelfen?

    • Hallo Lisam
      um die Korrektheit zu beweisen, musst du zeigen dass mit jedem Durchlauf der äußeren Schleife, der sortierte Anteil (also Teilliste 1) größer wird. Das mathematische Hilfsmittel hierfür ist ein Induktionsbeweis. Am Anfang hast du zwei Listen mit je einem Element, nach eventueller Vertauschung dieser Elemente hast du eine sortierte, die aus zwei Elementen besteht, somit gilt dein Induktionsanfang. Als Induktionsvoraussetzung kannst du dann annehmen, dass dein Array bereits bis zu einem Index i sortiert ist. Im Induktionsschritt musst du dann zeigen, dass du auch das i+1 Element an eine Position bringen kannst, sodass die Elemente 1…i+1 sortiert sind. Hier kommt es dann darauf wie stark man das aufdröseln möchte.Was wir in der while Schleife machen ist eigentlich nichts anderes als Bubblesort, von daher würde meiner Meinung nach hier ein Verweis auf die Korrektheit des Bubblesort reichen. Hilft das weiter? Viele Grüße Kim

  • Antworte

    Ja sehr, danke 🙂

  • Antworte

    Wie sehen die Formeln im besten oder im durchschnittsfall aus ?
    Beim schlechtesten ist die formel ja = (n-1)+(n-2)…..+2+1

    • Beim Insertion Sort hängt die Geschwindigkeit von der Sortiertheit deiner Liste ab. Der beste Fall ist, wenn die Liste bereits sortiert ist. Dann ist der Insertion Sort in n Schrittten fertig. Einen durchschnittlichen Wert anzugeben ist nicht so leicht, weil man dann eine durchschnittliche Sortierheit bräuchte. Man kann aber zeigen, dass der Insertion Sort im Durchschnitt von quadratischer Komplexität ist.

  • Antworte

    Dankeschön, das hat mir sehr geholfen!

  • Antworte

    Hallo schöner Artikel!
    Hilft mir vor der AuD Klausur gut weiter 😀
    Eine Frage: hängt die O-Notation von allen geläufigen Sortieralgorithmen von der Sortiertheit der Liste ab? Z.B. bei Selectionsort, Mergesort, Quicksort, Heapsort?
    LG

    • Hallo Carolin, vielen Dank! Nein, diese Eigenschaft haben viele Sortieralgorithmem aber nicht alle. Der Bubblesort meines Wissens nach z.B. nicht. Viele Grüße Kim

  • Antworte

    Hallo !! Wirklich sehr schön veranschaulicht, chapeau !

    • Hall Günther, ich freue ich wenn ich helfen konnte. Viele Grüße Kim

  • Antworte

    Hallo Kim, diese Ausführung ist sehr Ausführlich und hat mir sehr geholfen die Sortieralgorythmen im Informatikunterricht an meiner Schuke nachzuvollziehen. Deine Art der veranschaulichung hat mir sehr gefallen, weiter so!

    • Hallo Maximilian, freue mich wenn ich weiterhelfen kann. Viele Grüße Kim

  • Antworte

    Sogar in der Uni hilfreich 😉 Werde im Fach Algorithmen und Datenstrukturen noch öfters hier auf der Seite was nachlesen ;D
    Grüße aus Regensburg

    • Hallo Tim, freue mich, dass dir der Artikel weiterhelfen konnte. Viele Grüße Kim

  • Antworte

    Danke für deine supertolle Erklärung,Kim. Du bist hiermit offiziell ein EHRENMANN!!!

    • Dankeschön!

  • Antworte

    Kim, du bist ein großer Ehrenmann.

    Danke für diesen hilfreichen Artikel und generell für deine Arbeit und Mühe uns die Informatik zu erklären, die uns in der Uni erstmal recht kompliziert erscheint .
    Mach weiter so!:)

    • Herzlichen Dank!

Antworte auf Günther Abbruch