Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/InsertionSort

InsertionSort

Dieses Kapitel behandelt die Sortiermethode InsertionSort oder auch Sortieren durch Einfügen genannt. Die Idee des Algorithmus ist, die typische menschliche Vorgehensweise, etwa beim Sortieren eines Stapels von Karten umzusetzen. Das heißt es wird mit der ersten Karte ein neuer Stapel gestartet. Anschließend nimmt man jeweils die nächste Karte des Originalstapels und fügt diese an der richtigen Stelle im neuen Stapel ein.

Beispiel

Java Code

void  InsertionSort(int[] F) {  

int m,j;
for (int i = 1; i < F.length; i++){
      j = i;
      m = F[i];
      while (j > 0 && F[j-1] > m) {
             /*verschiebe F[j-1] nach rechts */
              F[j] = F[j-1];
              j--;
       }
       F[j] = m;
     }
}

Das Array hat F.length viele Elemente von Position 0 bis F.Length-1. Wenn F[j-1] größer m ist, dann wird F[j-1] nach rechts verschoben. Am Ende des Algorithmus wird F[i] an Position F[j] gesetzt.

Analyse

Theorem der Terminierung

Das Theorem der Terminierung besagt, dass der Algorithmus InsertionSort für jede Eingabe int[] F nach endlicher Zeit terminiert.

Beweis

Die Laufvariable i in der äußeren for‐Schleife wird in jedem Durchgang um eins erhöht und wird damit irgendwann die Abbruchbedingung (eine Konstante)erreichen. Die Laufvariable j der inneren while‐Schleife wird in jedem Durchgang um eins verringert und somit die Schleifenbedingung j>0 irgendwann nicht mehr erfüllen.

Theorem der Korrektheit

Das Theorem der Korrektheit besagt, dass der Algorithmus InsertionSort das Problem des vergleichsbasierten Sortierens löst. Beweisen

Beweis

Wir zeigen, dass die folgende Aussage eine Invariante der äußeren for‐Schleife ist (d.h. sie ist am Ende eines jeden Schleifendurchgangs gültig): Das Teilarray F[0..i] ist sortiert Damit gilt auch, dass nach Abbruch der for‐Schleife das Array F[0..n]=F (mit n=F.length‐1) sortiert ist. Zu zeigen ist nun, dass am Ende jeden Durchgangs der äußeren for Schleife F[0...i] sortiert ist. Dies wird durch Induktion nach i gezeigt. Für i=1 gilt im ersten Durchgang wird das erste Element F[0] mit dem zweiten Element F[1] verglichen und ggfs. getauscht um Sortierung zu erreichen (while‐Bedingung). Für $i\to i+1$ gilt angenommen F[0...i] ist am Anfang der äußeren for‐Schleife im Durchgang i+1 sortiert. In der while‐Schleife werden Elemente solange einen Platz weiter nach hinten verschoben, bis ein Index k erreicht wird, sodass alle Elemente mit Index 0..k‐1 kleiner/gleich dem ursprünglichen Element an Index i+1 sind (Induktionsbedingung) und alle Elemente mit Index k+1...i+1 größer sind (while‐Bedingung). Das ursprüngliche Element an Index i+1 wird dann an Position k geschrieben. Damit gilt, dass F[0...i+1] sortiert ist.

Theorem der Laufzeit

Das Theorem der Laufzeit besagt, dass die Anzahl der Vergleichsoperationen von Insertion Sort im besten Fall $\Theta (n)$ ist und im durchschnittlichen und schlechtesten $O(n^{2})$.

Beweis

Für die Aufwandsanalyse sind die Anzahl der Vertauschungen und der Vergleiche relevant. Allerdings dominieren die Vergleiche die Vertauschungen, das heißt es werden wesentlich mehr Vergleiche als Vertauschungen benötigt. Wir müssen in jedem Fall alle Elemente i:=1 bis n-1 durchgehen, d.h. immer Faktor n-1 für die Anzahl der Vergleiche. Dann müssen wir zur korrekten Einfügeposition zurückgehen

Im besten Fall ist die Liste schon sortiert. Die Einfügeposition ist gleich nach einem Schritt an Position i-1, d.h. die Anzahl der Vergleiche ist gleich der Anzahl der Schleifendurchläufe = n-1. Bei jedem Rückweg zur Einfügeposition nimmt man den Faktor 1. Somit beträgt die Gesamtzahl der Vergleiche: $(n-1)\cdot 1=n-1$. Für große Listen lässt sich $n-1\approx n$ abschätzen. Damit haben wir einen linearen Aufwand.

Im mittleren Fall ist die Liste unsortiert. Die Einfügeposition befindet sich wahrscheinlich auf der Hälfte des Rückwegs. Bei jedem der n-1 Rückwege, muss ein (i-1)/2 Vergleich addiert werden. Die Gesamtzahl der Vergleiche beträgt dann:

$(n-1)/2+(n-2)/2+(n-3)/2+...+2/2+1/2$

$={\frac {(n-1)+(n-2)+(n-3)+...+2+1}{2}}$

$={\frac {1}{2}}\cdot {\frac {n\cdot (n-1)}{2}}$

$={\frac {n\cdot (n-1)}{4}}$

$\approx {\frac {n^{2}}{4}}$

Daraus ergibt sich ein quadratischer Aufwand, wenn konstante Faktoren nicht berücksichtigt werden.

Im schlechtesten Fall ist die Liste absteigend sortiert. Die Einfügeposition befindet sich am Ende des Rückgabewertes bei Position 1. Bei jedem der n-1 Rückwege müssen i-1 Elemente verglichen werden (d.h. alle vorherigen Elemente F[1...i-1]). Analog zu vorhergehenden Überlegungen, gibt es hier aber die doppelte Rückweglänge. Daraus ergibt sich die Gesamtanzahl der Vergleiche:

$(n-1)+(n-2)+(n-3)+...+2+1$ $={\frac {n\cdot (n-1)}{2}}$ $\approx {\frac {n^{2}}{2}}$

Daraus ergibt sich ein quadratischer Aufwand, wenn konstante Faktoren nicht berücksichtigt werden.

Optimierung

In der vorgestellten Version des Algorithmus wird die Einfügeposition eines Elements durch (umgekehrte) sequenzielle Suche gefunden. Verwendet man hier binäre Suche (das Teilarray vor dem aktuellen Element ist sortiert!) kann die Anzahl der Vergleichsoperationen gesenkt werden zu O(n log n) (genauere Analyse zeigt, dass die Zahl noch kleiner ist)

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5.2.2 zu finden.