~2025-16077-1: /* Pseudocode */

2025-07-09T12:04:04Z

Pseudocode

Neue Seite

[[File:Insertion_sort.gif|mini|Animation von Insertionsort]]
'''Insertionsort''' (auch ''Sortieren durch Einfügen'', {{enS|insertion|de=das Einfügen}} und {{enS|sort|de=sortieren}}) ist ein einfaches [[Stabilität (Sortierverfahren)|stabiles]] [[Sortierverfahren]] (d. h., die Reihenfolge von Elementen mit gleichem Schlüsselwert bleibt unverändert). Es ist leicht zu implementieren, effizient bei kleinen oder bereits teilweise sortierten Eingabemengen. Außerdem benötigt Insertionsort keinen zusätzlichen Speicherplatz, da der Algorithmus ''[[in-place]]'' arbeitet. Ein weiterer Vorteil besteht darin, dass Insertionsort als [[Online-Algorithmus]] eingesetzt werden kann.

Der Insertionsort entnimmt der unsortierten Eingabefolge ein beliebiges Element und fügt es an richtiger Stelle in die (anfangs leere) Ausgabefolge ein. Geht man hierbei in der Reihenfolge der ursprünglichen Folge vor, so ist das Verfahren stabil. Wird auf einem [[Feld (Datentyp)|Array]] gearbeitet, so müssen die Elemente hinter dem neu eingefügten Element verschoben werden. Dies ist die eigentlich aufwendige Operation des Insertionsorts. Das Auffinden der richtigen Einfügeposition kann über eine [[binäre Suche]] vergleichsweise effizient erfolgen. Grundsätzlich gilt aber, dass Insertionsort weit weniger effizient arbeitet als andere anspruchsvollere Sortierverfahren.

== Problembeschreibung ==
Das Vorgehen ist mit der Sortierung eines Spielkartenblatts vergleichbar. Am Anfang liegen die Karten des Blatts verdeckt auf dem Tisch. Die Karten werden nacheinander aufgedeckt und an der korrekten Position in das Blatt, das in der Hand gehalten wird, eingefügt. Um die Einfügestelle für eine neue Karte zu finden, wird entweder die Karte sukzessive (von links nach rechts) mit den bereits einsortierten Karten des Blattes verglichen, oder eine binäre Suche durchgeführt. Zu jedem Zeitpunkt sind die Karten in der Hand sortiert und bestehen aus den bereits vom Tisch entnommenen Karten.
Zum Einfügen der neuen Karte müssen alle auf der Hand nachfolgenden eine Position weiter nach rechts wandern.

=== Eingabe ===
Eine Folge von <math>n</math> zu sortierenden Zahlen <math>\left(a_1,a_2,\ldots,a_n \right)</math>.

Die Zahlen werden auch als Schlüssel (keys) bezeichnet; diese sind oft nur ein Bestandteil eines Datensatzes.

== Implementierung ==

=== Pseudocode ===
Der folgende [[Pseudocode]] sortiert die Eingabefolge aufsteigend. Um eine absteigende Sortierung zu erreichen, ist der zweite Vergleich in Zeile 4 entsprechend zu ändern. Der Parameter <code>A</code> ist ein [[Feld (Datentyp)|Feld]] mit der zu Beginn unsortierten Folge. Nach Beendigung des Algorithmus enthält <code>A</code> mit den Elementen <code>A[0]</code>, <code>A[1]</code>, …, <code>A[n-1]</code> die sortierte Folge.<br />
Hierbei ist zu beachten, dass die Indizierung des [[Feld (Datentyp)|Feldes]] mit einer 0 beginnt.<br />
<math>n</math>: Anzahl der Elemente von <code>A</code><br />
<math>n-1</math>: Index des letzten Elementes von <code>A</code>

INSERTIONSORT(A)<br />
'''for''' i = 1 '''to''' Länge(A) '''do'''
einzusortierender_wert = A[i]
j = i
'''while''' (j > 0) '''and''' (A[j-1] > einzusortierender_wert) '''do'''
A[j] = A[j - 1]
j = j - 1
'''end while'''
A[j] = einzusortierender_wert
'''end for'''

'''Anmerkungen:'''
* Die Positionsvariable ''i'' kann bei 1 beginnen anstatt bei 0, da ein Sortieren erst beginnt, wenn wenigstens zwei Werte gegeben sind (''i''=0 und ''i''=1), erst dann kommt es zum ersten Vergleich. Davor kann A[0] als „bereits sortiert“ betrachtet werden.
* Die innere ''j''-while-Schleife verschiebt im bereits sortierten Bereich 0..(''i''-1) alle „zu große“ Elemente eine Position nach hinten. Dadurch ergibt sich an richtiger Stelle dann der eine Freiraum, um den einzusortierenden Wert einzufügen.

=== Struktogramm ===
Im Folgenden ein [[Nassi-Shneiderman-Diagramm]] (Struktogramm) des Insertionsort-Algorithmus. Die Bezeichner sind an obigen Pseudocode angelehnt.

{| class="toccolours" style="margin-left: 2em; border-collapse:collapse; border:2px solid gray;"
|-
|colspan="3" style="padding:5px;"| '''Zähle''' i '''von''' 1 '''bis''' n-1
|-
|rowspan="6" style="width:1.5em"|
|colspan="2" style="border:2px solid grey; padding:5px;"| einzusortierender_wert = A[ i ]
|-
|colspan="2" style="border:2px solid grey; padding:5px;"| j = i
|-
|colspan="2" style="border:2px solid grey; border-bottom:none; padding:5px;"| '''Solange''' j > 0 und A[ j-1 ] > einzusortierender_wert
|-
|rowspan="2" style="border-left: 2px solid gray; width:1.5em;"|
|style="border:2px solid grey; padding:5px;"| A[ j ] = A[ j-1 ]
|-
|style="border:2px solid grey; padding:5px;"| j = j - 1
|-
|colspan="2" style="border:2px solid grey; padding:5px;"| A[ j ] = einzusortierender_wert
|}

== Beispiel ==
Ausführung von Insertionsort auf Eingabefeld <math>A[0 .. 5]</math>. Die Komponente, auf die der Index <math>i</math> zeigt, ist rot eingefärbt. Blau eingefärbte Felder liegen im bereits sortierten Teilfeld <math>A[1 .. i-1]</math>.

{| class="wikitable centered" style="border:none;"
! style="border:none; width:20px; height:20px"| 0
! style="border:none; width:20px; height:20px"| 1
! style="border:none; width:20px; height:20px"| 2
! style="border:none; width:20px; height:20px"| 3
! style="border:none; width:20px; height:20px"| 4
! style="border:none; width:20px; height:20px"| 5
|- style="background:#FFD700; font-size:110%; text-align:center;"
| 5
| 2
| 4
| 6
| 1
| 3
|}

Da ein einzelnes Element keiner Ordnungsrelation unterliegt, beginnt der Index bei <math>i=1</math> und das zweite Element wird mit dem ersten verglichen.

{| class="wikitable centered" style="border:none;"
! style="border:none; width:20px; height:20px"| 0
! style="border:none; width:20px; height:20px"| 1
! style="border:none; width:20px; height:20px"| 2
! style="border:none; width:20px; height:20px"| 3
! style="border:none; width:20px; height:20px"| 4
! style="border:none; width:20px; height:20px"| 5
|- style="background:#FFD700; font-size:110%; text-align:center;"
|style="background:#87CEFF;"| 5
|style="background:#FFC1C1;"| 2
| 4
| 6
| 1
| 3
|}

{| class="wikitable centered" style="border:none;"
! style="border:none; width:20px; height:20px"| 0
! style="border:none; width:20px; height:20px"| 1
! style="border:none; width:20px; height:20px"| 2
! style="border:none; width:20px; height:20px"| 3
! style="border:none; width:20px; height:20px"| 4
! style="border:none; width:20px; height:20px"| 5
|- style="background:#FFD700; font-size:110%; text-align:center;"
|style="background:#87CEFF;"| 2
|style="background:#FFC1C1;"| 5
| 4
| 6
| 1
| 3
|}

Die 5 rutscht in der blauen sortierten Teilliste nach hinten und die 2 wird am Anfang dieser eingefügt. Damit sind die ersten beiden Elemente der Folge sortiert und das nächste Element wird überprüft (<math>i=2</math>).

{| class="wikitable centered" style="border:none;"
! style="border:none; width:20px; height:20px"| 0
! style="border:none; width:20px; height:20px"| 1
! style="border:none; width:20px; height:20px"| 2
! style="border:none; width:20px; height:20px"| 3
! style="border:none; width:20px; height:20px"| 4
! style="border:none; width:20px; height:20px"| 5
|- style="background:#FFD700; font-size:110%; text-align:center;"
|style="background:#87CEFF;"| 2
|style="background:#87CEFF;"| 5
|style="background:#FFC1C1;"| 4
| 6
| 1
| 3
|}

{| class="wikitable centered" style="border:none;"
! style="border:none; width:20px; height:20px"| 0
! style="border:none; width:20px; height:20px"| 1
! style="border:none; width:20px; height:20px"| 2
! style="border:none; width:20px; height:20px"| 3
! style="border:none; width:20px; height:20px"| 4
! style="border:none; width:20px; height:20px"| 5
|- style="background:#FFD700; font-size:110%; text-align:center;"
|style="background:#87CEFF;"| 2
|style="background:#87CEFF;"| 4
|style="background:#FFC1C1;"| 5
| 6
| 1
| 3
|}

Bei <math>i=3</math> ist nichts weiter zu tun, da 6 bereits die richtige Position am Ende der sortierten Teilliste hat.

{| class="wikitable centered" style="border:none;"
! style="border:none; width:20px; height:20px"| 0
! style="border:none; width:20px; height:20px"| 1
! style="border:none; width:20px; height:20px"| 2
! style="border:none; width:20px; height:20px"| 3
! style="border:none; width:20px; height:20px"| 4
! style="border:none; width:20px; height:20px"| 5
|- style="background:#87CEFF;font-size:110%; text-align:center;"
| 2
| 4
| 5
|style="background:#FFC1C1;"| 6
|style="background:#FFD700;"| 1
|style="background:#FFD700;"| 3
|}

Im vorletzten Schritt wird die 1 ausgewählt und in die sortierte Liste eingefügt. Dabei rutschen alle bisherigen sortierten Elemente in der sortierten Liste um eins nach hinten (<math>i=4</math>).

{| class="wikitable centered" style="border:none;"
! style="border:none; width:20px; height:20px"| 0
! style="border:none; width:20px; height:20px"| 1
! style="border:none; width:20px; height:20px"| 2
! style="border:none; width:20px; height:20px"| 3
! style="border:none; width:20px; height:20px"| 4
! style="border:none; width:20px; height:20px"| 5
|- style="background:#87CEFF;font-size:110%; text-align:center;"
| 2
| 4
| 5
| 6
|style="background:#FFC1C1;"| 1
|style="background:#FFD700;"| 3
|}

{| class="wikitable centered" style="border:none;"
! style="border:none; width:20px; height:20px"| 0
! style="border:none; width:20px; height:20px"| 1
! style="border:none; width:20px; height:20px"| 2
! style="border:none; width:20px; height:20px"| 3
! style="border:none; width:20px; height:20px"| 4
! style="border:none; width:20px; height:20px"| 5
|- style="background:#87CEFF;font-size:110%; text-align:center;"
| 1
| 2
| 4
| 5
|style="background:#FFC1C1;"| 6
|style="background:#FFD700;"| 3
|}

Im letzten Schritt wird die 3 an passender Position in die sortierte Teilliste gebracht (<math>i=5</math>).

{| class="wikitable centered" style="border:none;"
! style="border:none; width:20px; height:20px"| 0
! style="border:none; width:20px; height:20px"| 1
! style="border:none; width:20px; height:20px"| 2
! style="border:none; width:20px; height:20px"| 3
! style="border:none; width:20px; height:20px"| 4
! style="border:none; width:20px; height:20px"| 5
|- style="background:#87CEFF;font-size:110%; text-align:center;"
| 1
| 2
| 4
| 5
| 6
|style="background:#FFC1C1;"| 3
|}

{| class="wikitable centered" style="border:none;"
! style="border:none; width:20px; height:20px"| 0
! style="border:none; width:20px; height:20px"| 1
! style="border:none; width:20px; height:20px"| 2
! style="border:none; width:20px; height:20px"| 3
! style="border:none; width:20px; height:20px"| 4
! style="border:none; width:20px; height:20px"| 5
|- style="background:#87CEFF;font-size:110%; text-align:center;"
| 1
| 2
| 3
| 4
| 5
|style="background:#FFC1C1;"| 6
|}

Nach dem Algorithmus sind alle Felder der Folge sortiert.

{| class="wikitable centered" style="border:none;"
! style="border:none; width:20px; height:20px"| 0
! style="border:none; width:20px; height:20px"| 1
! style="border:none; width:20px; height:20px"| 2
! style="border:none; width:20px; height:20px"| 3
! style="border:none; width:20px; height:20px"| 4
! style="border:none; width:20px; height:20px"| 5
|- style="background:#87CEFF; font-size:110%; text-align:center;"
| 1
| 2
| 3
| 4
| 5
| 6
|}

== Komplexität ==
Die Anzahl der Vergleiche und Verschiebungen des Algorithmus ist von der Anordnung der Elemente in der unsortierten Eingangsfolge abhängig. Für den [[Average Case]] ist eine genaue Abschätzung der Laufzeit daher schwierig, man kann aber zeigen, dass der Average Case in <math>\mathcal{O}(n^2)</math> liegt. Im [[Best Case]], wenn das Eingabearray bereits sortiert ist, ist die Komplexität linear <math> \mathcal{O}(n)</math>, d. h. sogar besser als bei den komplizierteren Verfahren ([[Quicksort]], [[Mergesort]], [[Heapsort]] etc.). Im [[Worst Case]] ist sie quadratisch <math>\mathcal{O}(n^2)</math>.

Wenn zur Bestimmung der richtigen Position eines Elementes die binäre Suche benutzt wird, kann man die Anzahl der Vergleiche im Worst Case durch
:<math>\log(n!) \in \mathcal{O}(n \log n-n \log e+\log n) = \mathcal{O}(n\log n-0{,}4426n+\log n)</math>
abschätzen; dabei geht aber ggf. die Stabilität des Sortierverfahrens verloren.

Die Anzahl der Schiebeoperationen im Average Case beträgt
:<math>n (n-1)/4 \in \mathcal{O}(n^2)</math>.
Der Worst Case ist ein absteigend sortiertes Array <math>A</math>, da jedes Element von seiner Ursprungsposition <math>j</math> bis auf die erste Arrayposition verschoben wird und dabei <math>j-1</math> Verschiebeoperationen nötig sind. Deren Gesamtanzahl beträgt somit
:<math>n (n-1)/2 \in \mathcal{O}(n^2)</math>.

== Weiterentwicklung ==
[[Donald L. Shell]] schlug eine substanzielle Verbesserung dieses Algorithmus vor, die heute unter dem Namen [[Shellsort]] bekannt ist. Statt benachbarter Elemente werden Elemente, die durch eine bestimmte Distanz voneinander getrennt sind, verglichen. Diese Distanz wird bei jedem Durchgang verringert. Aufgrund der Sortierung über Distanz verliert die Sortiermethode ihre Eigenschaft „stabil“.

[[Robert Sedgewick (Informatiker)|Robert Sedgewick]] veröffentlichte eine optimierte Implementierung von Insertionsort, welche einen [[Sentinel (Programmierung)|Sentinel]] verwendet und nur die Hälfte an Vertauschungen benötigt. Nachfolgend wird diese Optimierung durch eine „papyrus script function“ veranschaulicht. Float[] a ist beispielhaft ein Array mit Fließkommazahlen. Die beiden integer-Parameter stellen den flexiblen Sortierbereich für das Array dar (Startwert „L“, Endwert „R“). Angenommen das Array hat 100 Elemente und beginnt bei 1, dann muss L=1 und R=100 gesetzt werden, um es vollständig zu sortieren.

'''FUNCTION''' SortByInsert(Float[] a, Int L, Int R)
1 '''bool''' bOK
2 '''float''' X ; Comparable v
3 '''float''' f
4
5 '''int''' k = -1 ; original: k = 0 // counter of exchanges
6 '''int''' i = R ; original: R - 1
7 X = a[i] ; Sentinel
8 '''WHILE''' (i > L) ; TopDown loop
9 f = a[i - 1]
10 '''IF''' (X < f)
11 a[i - 1] = X ; exchange
12 a[i] = f
13 k = i ; original: k = k + 1
14 '''ELSE'''
15 X = f ; no exchange/swap, update Sentinel only
16 '''ENDIF'''
17 i = i - 1
18 '''ENDWHILE'''
19
20 '''IF''' (k < 0)
21 '''RETURN''' ; - STOP - short circuit, no exchanges made
22 '''ENDIF'''
23 ; -------------------------- "insertion sort with half-exchanges"
24 i = L + 2
25 '''WHILE''' (i <= R) ; original: (i < R)
26 X = a[i] ; Sentinel
27 k = i ; original: j = i // counter for insertions
28 bOK = '''TRUE'''
29 '''WHILE''' (bOK)
30 f = a[k - 1]
31 '''IF''' (X < f)
32 a[k] = f
33 k = k - 1
34 '''ELSE'''
35 bOK = False
36 '''ENDIF'''
37 '''ENDWHILE'''
38 '''IF''' (k < i)
39 a[k] = X ; original: a[j] = v
40 '''ENDIF'''
41 i = i + 1
42 '''ENDWHILE'''
'''ENDFUNCTION'''

== Siehe auch ==
* [[Liste von Algorithmen]]

== Weblinks ==
* [http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/insert/insertion.htm Beschreibung des Algorithmus und Simulation] ([[Java-Applet]])
* [http://algs4.cs.princeton.edu/21elementary/InsertionX.java.html Optimierter InsertionSort mit Sentinel]

[[Kategorie:Sortieralgorithmus]]

Insertionsort - Versionsgeschichte

~2025-16077-1: /* Pseudocode */