German English
Sorting method
Insertion site
Insertion sort (sorting by insertion) is an elementary sorting method. It has a time complexity of
)
Θ(n 2 , so it is slower than Heapsort , Mergesort or Shellsort . Insertion sort is very suitablefor
sorting small amounts of data or for inserting additional elements into an already sorted
sequence.
idea
At the beginning and after each step of the process, the sequence a , ..., a n to be sorted
0 -1
consists of two parts: The first part a , ..., a i is already sorted in ascending order, the
0 -1
second part a i , ..., a n is still unsorted.
-1
The element a i is next inserted into the already sorted part by comparing it in turn with a i ,ai
-1
As soon as an element a j with a j ≤ a i is found, a i is inserted after it. If no such element
-2 , etc.
is found, a i is placed at the beginning of the sequence.
This means that the sorted part has become one element longer. In the next step, a i is
+1
inserted into the sorted part, etc. Initially, the sorted part only consists of the element a ; finally
0
from all elements a , ..., a n .
0 -1
Example: The following table shows the sorting steps for sorting the sequence 5 7 0 3 4 2 6 1.
The part of the sequence that has already been sorted is shown in green on the left. On the
far right, in brackets, is the number of positions by which the inserted element moved to the
left.
5 7 0 3 4 2 6 1 (0)
5 7 0 3 4 2 6 1 (0)
0 5 7 3 4 2 6 1 (2)
0 3 5 7 4 2 6 1 (2)
0 3 4 5 7 2 6 1 (2)
0 2 3 4 5 7 6 1 (4)
0 2 3 4 5 6 7 1 (1)
0 1 2 3 4 5 6 7 (6)
implementation
The following insertionsort function sorts an integer array a [0], ..., a [ n -1].
The sorting function is encapsulated in the InsertionSorter class. With the instructions
InsertionSorter s= new InsertionSorter();
[Link](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=[Link];
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ügeposition 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ügeposition 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 Indexpositionen, 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 beispielsweise 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 Inversionenfolge bezeichnet.
Definition: Die Inversionenfolge 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 Inversionenfolge v = 0, 0, 2, 0, 1.
Offensichtlich 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 Inversionenfolge 0, ..., n-1.
Satz: Sei a = a0, ..., an-1 eine Folge und v = v0, ..., vn-1 ihre Inversionenfolge. Dann ist die
Anzahl der Schritte, die Insertionsort zum Sortieren der Folge benötigt
T(a) = i = 0, ..., n-1 vi
Beweis: Offensichtlich 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 Anfangsbeispiel und die zugehörige
Inversionenfolge.
i 0 1 2 3 4 5 6 7
ai 5 7 0 3 4 2 6 1
vi 0 0 2 2 2 4 1 6
Beispielsweise 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:
a. Geben Sie die Permutation an, die zu der Inversionenfolge 0 0 0 3 3 3 3 3 gehört.
b. Geben Sie die Inversionenfolge derjenigen Permutation an, die durch Rechts-
Ringschieben der Folge 0, ..., n-1 um k < n Positionen entsteht.
c. Welche Folge der Länge 8 von Nullen und Einsen hat die maximale Anzahl von
Inversionen?
Aufgabe 2:
a. Zeigen Sie: Werden in einer Folge zwei benachbarte Zahlen vertauscht, so verändert
sich die Anzahl der Inversionen der Folge um höchstens 1.
b. Wie viele Vertauschungsschritte benötigt ein Sortierverfahren, 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 gleichbedeutend mit der Anweisungsfolge 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 Themen des Buches: Textsuche, Graphenalgorithmen, Arithmetik, Codierung,
Kryptografie, parallele Sortieralgorithmen.
[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]
HW Lang mail@[Link] Imprint Data protection
Created: January 31, 1998 Updated: February 5, 2023 These websites were created
during my teaching position at Flensburg University