Sortierverfahren

Insertionsort

 English version  aufwärts

Insertionsort (Sortieren durch Einfügen) ist ein elementares Sortier­verfahren. Es hat eine Zeit­komplexität von Θ(n2), ist damit also langsamer als etwa Heapsort, Mergesort oder auch Shellsort. Sehr gut geeignet ist Insertionsort für das Sortieren von kleinen Datenmengen oder für das Einfügen von weiteren Elementen in eine schon sortierte Folge.

Idee

Zu Anfang und nach jedem Schritt des Verfahrens besteht die zu sortierende Folge a0, ..., an-1 aus zwei Teilen: Der erste Teil a0, ..., ai-1 ist bereits aufsteigend sortiert, der zweite Teil ai, ..., an-1 ist noch unsortiert.

Das Element ai wird als nächstes in den bereits sortierten Teil eingefügt, indem es der Reihe nach mit ai-1, ai-2 usw. verglichen wird. Sobald ein Element aj mit ajkleiner gleichai gefunden wird, wird ai hinter diesem eingefügt. Wird kein solches Element gefunden, wird ai an den Anfang der Folge gesetzt.

Damit ist der sortierte Teil um ein Element länger geworden. Im nächsten Schritt wird ai+1 in den sortierten Teil eingefügt usw. Zu Anfang besteht der sortierte Teil nur aus dem Element a0; zum Schluss aus allen Elementen a0, ..., an-1.

Beispiel:  Die folgende Tabelle zeigt die Sortier­schritte zum Sortieren der Folge 5 7 0 3 4 2 6 1. Auf der linken Seite grün dargestellt befindet sich jeweils der bereits sortierte Teil der Folge. Ganz rechts steht in Klammern die Anzahl der Positionen, um die das eingefügte Element nach links gewandert ist.

57034261 (0)
57034261 (0)
05734261 (2)
03574261 (2)
03457261 (2)
02345761 (4)
02345671 (1)
01234567 (6)

Implementierung

Anhand der folgenden Simulation ist ersichtlich, wie das Verfahren realisiert wird. Im Anschluss daran folgt die ent­sprechende Umsetzung in ein Programm.

Simulation von Insertionsort

(Java-Applet zur Simulation von Insertionsort)

 

Die folgende Funktion insertionsort sortiert ein Integer-Array a[0], ..., a[n-1].

Die Sortier­funktion ist in der Klasse InsertionSorter gekapselt. Mit den Anweisungen

InsertionSorter s=new InsertionSorter();
s.sort(b);

wird ein Objekt vom Typ InsertionSorter erzeugt und anschließend die Methode sort zum Sortieren eines Arrays b aufgerufen.

 

public class InsertionSorter
{
    private int[] a;
    private int n;

    public void sort(int[] a)
    {
        this.a=a;
        n=a.length;
        insertionsort();
    }

    private void insertionsort()
    {
        int i, j, t;
        for (i=1; i<n; i++)
        {
            j=i;
            t=a[j];
            while (j>0 && a[j-1]>t)
            {
                a[j]=a[j-1];
                j--;
            }
            a[j]=t;
        }
    }

}    // end class InsertionSorter

Analyse

Im schlechtesten Fall wird der Platz für das einzufügende Element immer erst ganz am Anfang des sortierten Teils gefunden. D.h. in der While-Schleife werden Folgen der Länge 1, 2, 3, ..., n-1 durchsucht. Insgesamt sind dies (n-1)·n / 2 Schritte, also Θ(n2) Schritte. Dieser Fall tritt ein, wenn die Folge zu Anfang in absteigender Reihenfolge sortiert ist.

Es ginge auch schneller, die Einfüge­position des Elements ai innerhalb des sortierten Teils a0, ..., ai-1 zu finden, nämlich mit binärer Suche. Da aber die größeren Elemente alle nach rechts rücken müssen, um die Einfüge­position frei zu machen, ist für das Einfügen ohnehin lineare Zeit erforderlich.

 

Die genaue Anzahl der Schritte, die Insertionsort benötigt, wird durch die Anzahl der Inversionen der zu sortierenden Folge bestimmt.

Definition:  Sei a  =  a0, ..., an-1 eine endliche Folge. Eine Inversion ist ein Paar (i, j) mit i < j und ai > aj. Eine Inversion ist also ein Paar von Index­positionen, an denen die Elemente der Folge in falscher Reihenfolge stehen.1)

Beispiel:  Sei a = 5, 7, 4, 9, 7. Dann ist (0, 2) eine Inversion, denn es ist a0 > a2, nämlich 5 > 4. Außerdem sind (1, 2) und (3, 4) Inversionen, da 7 > 4 und 9 > 7. Weitere Inversionen sind nicht vorhanden.

Wir bestimmen nun die Anzahl der Inversionen (i, j) der Folge a getrennt für jede Position j. Ergebnis ist jeweils ein Wert vj, der die Anzahl der Elemente ai angibt, die links von aj stehen und größer sind als aj.

In der Folge a = 5, 7, 4, 9, 7 stehen beispiels­weise links von a2 = 4 die zwei größeren Zahlen 5 und 7, also ist v2 = 2. Links von a4 = 7 steht nur eine größere Zahl, also ist v4 = 1.

Die Folge der vj wird als Inversionen­folge bezeichnet.

Definition:  Die Inversionen­folge v = v0, ..., vn-1 einer Folge a = a0, ..., an-1 ist definiert durch

vj  =  |{ (i, j)  |  i < j   und   ai > aj }|

für j = 0, ..., n-1.

Beispiel:  Die obige Folge a = 5, 7, 4, 9, 7 hat die Inversionen­folge v = 0, 0, 2, 0, 1.

 

Offen­sichtlich gilt vikleiner gleichi für alle i = 0, ..., n-1. Genau dann, wenn alle vi gleich 0 sind, ist die zugehörige Folge a sortiert. Ist die Folge a eine Permutation, so ist sie durch ihre Inversionen­folge v eindeutig bestimmt. Die Permutation n-1, ..., 0 hat die Inversionen­folge 0, ..., n-1.

Satz:  Sei a = a0, ..., an-1 eine Folge und v = v0, ..., vn-1 ihre Inversionen­folge. Dann ist die Anzahl der Schritte, die Insertionsort zum Sortieren der Folge benötigt

T(a)  =   Summe i = 0, ..., n-1  vi

Beweis:  Offen­sichtlich benötigt Insertionsort in jeder Iteration i gerade vi Schritte, um das Element ai einzufügen. Daher ist die Gesamtzahl der benötigten Schritte gleich der Summe aller vi.

Beispiel:  Die folgende Tabelle zeigt die Folge a aus dem Anfangs­beispiel und die zugehörige Inversionen­folge.

i01234567
ai57034261
vi00222416

Beispiels­weise ist v5 = 4, weil vier Elemente links von a5 = 2 stehen, die größer als 2 sind (nämlich 5, 7, 3 und 4). Entsprechend benötigt Insertionsort zum Einfügen der 2 genau 4 Schritte.

Die Summe aller vi, also die Gesamtzahl aller Inversionen, ist 17. Insertionsort benötigt also zum Sortieren der Folge 17 Schritte.

Aufgaben

Aufgabe 1:  

  1. Geben Sie die Permutation an, die zu der Inversionen­folge 0 0 0 3 3 3 3 3 gehört.
  2. Geben Sie die Inversionen­folge derjenigen Permutation an, die durch Rechts-Ringschieben der Folge 0, ..., n-1 um k<n Positionen entsteht.
  3. Welche Folge der Länge 8 von Nullen und Einsen hat die maximale Anzahl von Inversionen?

Aufgabe 2:  

  1. Zeigen Sie: Werden in einer Folge zwei benachbarte Zahlen vertauscht, so verändert sich die Anzahl der Inversionen der Folge um höchstens 1.
  2. Wie viele Ver­tauschungsschritte benötigt ein Sortier­verfahren, das nur benachbarte Zahlen vertauscht (wie etwa Bubblesort), im schlechtesten Fall mindestens, um eine Folge der Länge n zu sortieren?

Literatur

[Knu 73]D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)
[Sed 88]R. Sedgewick: Algorithms. 2. Auflage, Addison-Wesley (1988)
[Lan 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Insertionsort und andere Sortierverfahren, so etwa Quicksort, Heapsort, Mergesort und Shellsort, finden Sie auch in meinem Buch über Algorithmen.
Weitere(vertikaler Abstand) Themen des Buches: Textsuche, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  

1)  Wenn die Folge a eine Permutation ist, lässt sich eine Inversion auch durch (ai, aj) anstelle von (i, j) angeben [Knu 73].

 

Weiter mit:   [Quicksort]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 31.01.1998   Updated: 03.03.2017
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik