Sortierverfahren

Insertionsort

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 aj ≤ ai 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.

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

Implementierung

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()
    {
        for (int i=1; i<n; i++)
        {
            int j=i;
            int t=a[j];
            while (j>=1 && a[j-1]>t)
            {
                a[j]=a[j-1];
                j--;
            }
            a[j]=t;
        }
    }
}

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   ∧   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 vi ≤ i 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)  =   Summei = 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.

i  01234567
ai  57034261
vi  00222416

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 Vertauschungs­schritte 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?

 

Strukturierte Implementierung

Das Programm lässt sich noch besser strukturieren, indem das Einsortieren eines Elements t in das schon sortierte Anfangsstück a0, ..., ai-1 in eine Funktion insert ausgelagert wird. Das Element t kommt an die Position i, wenn ai-1 kleiner oder gleich t ist; wenn dagegen ai-1 größer als t ist, rückt ai-1 nach rechts und i wird um 1 vermindert – solange wie i ≥ 1 gilt.

Das Nach-Rechts-Rücken ist hier etwas speziell implementiert: Die Anweisung a[i]=a[--i]; ist gleich­bedeutend mit der Anweisungs­folge a[i]=a[i-1]; i=i-1;.

 

    private void insert(int t, int i)
    {
        while (i>=1 && a[i-1]>t)
            a[i]=a[--i];
        a[i]=t;
    }

    private void insertionsort()
    {
        for (int i=1; i<n; i++)
            insert(a[i], i);
    }

 

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.

Buch

[Weitere Informationen]

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]

 

H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Created: 31.01.1998   Updated: 05.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden