„Insertionsort“ – Versionsunterschied

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Versionsgeschichte interaktiv durchsuchen
[gesichtete Version][ungesichtete Version]
← Zum vorherigen VersionsunterschiedZum nächsten Versionsunterschied →
Inhalt gelöscht Inhalt hinzugefügt
VisuellWikitext
"ortsfest" ist afaics eher ungebraeuchlich
AZ: Die Seite wurde geleert.
Zeile 1: Zeile 1:
'''Insertionsort''' ({{EnS|''insertion''}} ‚Einfügen‘ und {{EnS|''sort''}} ‚sortieren‘) ist ein einfaches [[Stabiles Sortierverfahren|stabiles]] Sortierverfahren. Es ist einfach zu implementieren, effizient bei (ziemlich) kleinen Eingabemengen, effizient bei Eingabemengen, die schon vorsortiert sind, stabil (d. h. die Reihenfolge von Elementen mit gleichem Schlüsselwert bleibt unverändert) und minimal im Speicherverbrauch, da der Algorithmus [[in-place]] arbeitet.

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 [[Stabiles Sortierverfahren|stabil]]. Wird auf einem Array gearbeitet, so müssen die Elemente hinter dem neu eingefügten Element verschoben werden. Dies ist die eigentlich aufwändige Operation von Insertionsort, da das Finden der richtigen Einfügeposition über eine [[binäre Suche]] vergleichsweise effizient erfolgen kann. Grundsätzlich jedoch ist Insertionsort weit weniger effizient 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 diese sukzessive (von links nach rechts) mit den bereits einsortierten Karten des Blattes verglichen. Zu jedem Zeitpunkt sind die Karten in der Hand sortiert und bestehen aus den zuerst vom Tisch entnommenen Karten.

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

=== Ausgabe ===
Umordnung <math>(a'_1, a'_2, \ldots, a'_n)</math> der Eingabefolge mit der Eigenschaft <math>a'_1 \leq a'_2 \leq \ldots \leq a'_n</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 <math>A</math> ist ein Feld mit der zu Beginn unsortierten Folge. Nach Beendigung des Algorithmus enthält <math>A</math> die sortierte Folge.
<code>
INSERTIONSORT(A)
1 '''for''' i ← 2 '''to''' länge(A)
2 '''do''' einzusortierender_wert ← A[i]
3 j ← i
4 '''solange''' j > 1 '''und''' A[j-1] > einzusortierender_wert
5 '''do''' A[j] ← A[j - 1]
6 j ← j − 1
7 A[j] ← einzusortierender_wert
</code>

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

:{| border="2" cellspacing="0" cellpadding="4" class="hintergrundfarbe1 rahmenfarbe1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; empty-cells:show"
|-
| colspan="3" style="border-bottom-style:none" | '''Zähle''' <math>i</math> von 2 bis <math>n</math>
|-
| style="border-top-style:none;border-bottom-style:none" |
| colspan="2" | einzusortierender_wert ← A[i]
|-
| style="border-top-style:none;border-bottom-style:none" |
| colspan="2" | j ← i
|-
| style="border-top-style:none;border-bottom-style:none" |
| colspan="2" style="border-bottom-style: none" | '''Solange''' <math>j > 1</math> und A[j-1] > einzusortierender_wert
|-
| style="border-top-style:none;border-bottom-style:none" |
| style="border-top-style:none;border-bottom-style:none" |
| A[j] ← A[j-1]
|-
| style="border-top-style:none;border-bottom-style:none" |
| style="border-top-style:none;border-bottom-style:none" |
| <math>j \leftarrow j - 1</math>
|-
| style="border-top-style:none;border-bottom-style:none" |
| colspan="2" | A[j] ← einzusortierender_wert
|-
| colspan="3" style="border-top-style:none" |
|}

== Beispiel ==
Ausführung von Insertionsort auf Eingabefeld <math>A[1 .. 6]</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-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;"
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 1
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 2
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 3
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 4
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 5
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 6
|-
| style="background-color:#ffd700;" align="center" | <big>5</big>
| style="background-color:#ffd700;" align="center" | <big>2</big>
| style="background-color:#ffd700;" align="center" | <big>4</big>
| style="background-color:#ffd700;" align="center" | <big>6</big>
| style="background-color:#ffd700;" align="center" | <big>1</big>
| style="background-color:#ffd700;" align="center" | <big>3</big>
|}

Das erste Element wird als sortiert angenommen und anschließend das zweite geprüft (<math>i=2</math>).

{| class="wikitable centered" style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;"
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 1
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 2
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 3
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 4
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 5
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 6
|-
| style="background-color:#87ceff;" align="center" | <big>5</big>
| style="background-color:#ffc1c1;" align="center" | <big>2</big>
| style="background-color:#ffd700;" align="center" | <big>4</big>
| style="background-color:#ffd700;" align="center" | <big>6</big>
| style="background-color:#ffd700;" align="center" | <big>1</big>
| style="background-color:#ffd700;" align="center" | <big>3</big>
|}

{| class="wikitable centered" style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;"
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 1
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 2
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 3
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 4
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 5
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 6
|-
| style="background-color:#87ceff;" align="center" | <big>2</big>
| style="background-color:#ffc1c1;" align="center" | <big>5</big>
| style="background-color:#ffd700;" align="center" | <big>4</big>
| style="background-color:#ffd700;" align="center" | <big>6</big>
| style="background-color:#ffd700;" align="center" | <big>1</big>
| style="background-color:#ffd700;" align="center" | <big>3</big>
|}

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=3</math>).

{| class="wikitable centered" style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;"
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 1
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 2
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 3
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 4
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 5
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 6
|-
| style="background-color:#87ceff;" align="center" | <big>2</big>
| style="background-color:#87ceff;" align="center" | <big>5</big>
| style="background-color:#ffc1c1;" align="center" | <big>4</big>
| style="background-color:#ffd700;" align="center" | <big>6</big>
| style="background-color:#ffd700;" align="center" | <big>1</big>
| style="background-color:#ffd700;" align="center" | <big>3</big>
|}

{| class="wikitable centered" style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;"
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 1
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 2
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 3
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 4
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 5
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 6
|-
| style="background-color:#87ceff;" align="center" | <big>2</big>
| style="background-color:#87ceff;" align="center" | <big>4</big>
| style="background-color:#ffc1c1;" align="center" | <big>5</big>
| style="background-color:#ffd700;" align="center" | <big>6</big>
| style="background-color:#ffd700;" align="center" | <big>1</big>
| style="background-color:#ffd700;" align="center" | <big>3</big>
|}

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

{| class="wikitable centered" style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;"
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 1
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 2
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 3
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 4
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 5
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 6
|-
| style="background-color:#87ceff;" align="center" | <big>2</big>
| style="background-color:#87ceff;" align="center" | <big>4</big>
| style="background-color:#87ceff;" align="center" | <big>5</big>
| style="background-color:#ffc1c1;" align="center" | <big>6</big>
| style="background-color:#ffd700;" align="center" | <big>1</big>
| style="background-color:#ffd700;" align="center" | <big>3</big>
|}

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=5</math>).

{| class="wikitable centered" style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;"
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 1
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 2
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 3
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 4
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 5
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 6
|-
| style="background-color:#87ceff;" align="center" | <big>2</big>
| style="background-color:#87ceff;" align="center" | <big>4</big>
| style="background-color:#87ceff;" align="center" | <big>5</big>
| style="background-color:#87ceff;" align="center" | <big>6</big>
| style="background-color:#ffc1c1;" align="center" | <big>1</big>
| style="background-color:#ffd700;" align="center" | <big>3</big>
|}

{| class="wikitable centered" style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;"
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 1
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 2
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 3
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 4
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 5
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 6
|-
| style="background-color:#87ceff;" align="center" | <big>1</big>
| style="background-color:#87ceff;" align="center" | <big>2</big>
| style="background-color:#87ceff;" align="center" | <big>4</big>
| style="background-color:#87ceff;" align="center" | <big>5</big>
| style="background-color:#ffc1c1;" align="center" | <big>6</big>
| style="background-color:#ffd700;" align="center" | <big>3</big>
|}

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

{| class="wikitable centered" style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;"
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 1
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 2
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 3
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 4
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 5
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 6
|-
| style="background-color:#87ceff;" align="center" | <big>1</big>
| style="background-color:#87ceff;" align="center" | <big>2</big>
| style="background-color:#87ceff;" align="center" | <big>4</big>
| style="background-color:#87ceff;" align="center" | <big>5</big>
| style="background-color:#87ceff;" align="center" | <big>6</big>
| style="background-color:#ffc1c1;" align="center" | <big>3</big>
|}

{| class="wikitable centered" style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;"
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 1
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 2
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 3
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 4
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 5
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 6
|-
| style="background-color:#87ceff;" align="center" | <big>1</big>
| style="background-color:#87ceff;" align="center" | <big>2</big>
| style="background-color:#87ceff;" align="center" | <big>3</big>
| style="background-color:#87ceff;" align="center" | <big>4</big>
| style="background-color:#87ceff;" align="center" | <big>5</big>
| style="background-color:#ffc1c1;" align="center" | <big>6</big>
|}

Nach dem Algorithmus sind alle Felder der Folge sortiert.

{| class="wikitable centered" style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;"
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 1
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 2
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 3
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 4
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 5
! style="border-top: 0pt solid; border-left: 0pt solid; border-right: 0pt solid;" width="20px" height="20px" | 6
|-
| style="background-color:#87ceff;" align="center" | <big>1</big>
| style="background-color:#87ceff;" align="center" | <big>2</big>
| style="background-color:#87ceff;" align="center" | <big>3</big>
| style="background-color:#87ceff;" align="center" | <big>4</big>
| style="background-color:#87ceff;" align="center" | <big>5</big>
| style="background-color:#87ceff;" align="center" | <big>6</big>
|}

== 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. Im [[Best Case]], wenn das Eingabearray bereits sortiert ist, ist die Komplexität linear <math> \mathcal{O}(n)</math>, d.&nbsp;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.
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-n \in \mathcal{O}(n^2)</math>.

== Weiterentwicklung ==
D. 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.

== 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]])

[[Kategorie:Sortieralgorithmus]]

[[ar:ترتيب بالإدراج]]
[[cs:Insertion sort]]
[[da:Indsættelsessortering]]
[[en:Insertion sort]]
[[es:Ordenamiento por inserción]]
[[et:Vahelepanemisega sortimine]]
[[fa:مرتب‌سازی درجی]]
[[fi:Lisäyslajittelu]]
[[fr:Tri par insertion]]
[[he:מיון הכנסה]]
[[hu:Beszúrásos rendezés]]
[[is:Innsetningarröðun]]
[[it:Insertion sort]]
[[ja:挿入ソート]]
[[ko:삽입 정렬]]
[[lt:Įterpimo rikiavimo algoritmas]]
[[ml:ഇൻസർഷൻ സോർട്ട്]]
[[nl:Insertion sort]]
[[no:Sorteringsalgoritme#Innstikksortering]]
[[pl:Sortowanie przez wstawianie]]
[[pt:Insertion sort]]
[[ru:Сортировка вставками]]
[[sk:Triedenie priamym vkladaním]]
[[sl:Urejanje z navadnim vstavljanjem]]
[[sv:Insättningssortering]]
[[th:การเรียงลำดับแบบแทรก]]
[[tr:Eklemeli sıralama]]
[[uk:Сортування включенням]]
[[vi:Sắp xếp chèn]]
[[zh:插入排序]]

Version vom 24. November 2010, 12:52 Uhr

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Insertionsort&oldid=81876698“