Insertionsort
aus Wikipedia, der freien Enzyklopädie
Insertionsort (engl. insertion - Einfügen) ist ein einfaches stabiles Sortierverfahren. Es ist weit weniger effizient als andere anspruchsvollere Sortierverfahren. Dafür hat es jedoch folgende Vorteile:
- einfach zu implementieren
- effizient bei (ziemlich) kleinen Eingabemengen
- effizient bei Eingabemengen, die schon vorsortiert sind
- stabil (d.h., die Reihenfolge von schon sortierten Elementen ändert sich nicht)
- minimaler Speicherverbrauch, da er ortsfest arbeitet
Inhaltsverzeichnis |
[Bearbeiten] Prinzip
Der Algorithmus entnimmt der unsortierten Eingabemenge ein beliebiges (z. B. das Erste) Element und fügt es an richtiger Stelle in die (anfangs leere) Ausgabemenge ein. Geht man in der Reihenfolge der ursprünglichen Menge vor, so ist es außerdem stabil. Wird auf einem Array gearbeitet, so müssen die Elemente nach dem neu eingefügten Element verschoben werden. Dies ist die eigentlich teure Operation von Insertionsort, da das Finden der richtigen Einfügeposition über eine binäre Suche vergleichsweise effizient erfolgen kann.
[Bearbeiten] Pseudocode
Der folgende Pseudocode sortiert die Eingabemenge aufsteigend. Um eine absteigende Sortierung zu erreichen, ist der zweite Vergleich in Zeile 4 entsprechend zu ändern.
a: Liste (Array) mit der unsortierten Eingabemenge insertion_sort(a) 1 von j2 bis länge[a] 2 führe aus aktueller_wert
[Bearbeiten] Struktogramm
Im folgenden ein Nassi-Shneiderman-Diagramm (Struktogramm) des Insertionsort-Algorithmus:
[Bearbeiten] Beispiel
Hier ein Beispiel anhand einer zu sortierenden Menge aus 5 Integer-Werten:
unsortierte Eingabemenge: [ 3 2 5 1 4 ]
-------------------------------------------------------------------------------
[| 3 2 5 1 4] Das erste Element wird der Eingabemenge entnommen und
^ zwischengespeichert.
[_ | 2 5 1 4] Alle in der Ausgabemenge vorhandenen größeren
Elemente werden, vom Ende der Ausgabemenge beginnend,
um jeweils eine Stelle nach rechts verschoben.
Dabei wird das zwischengespeicherte Element in der
Eingabemenge überschrieben.
[3 | 2 5 1 4] Das zwischengespeicherte Element wird in das durch
die Verschiebung der Elemente in der Ausgabemenge
freigewordene Feld geschrieben.
-------------------------------------------------------------------------------
[3 | 2 5 1 4] Das nächste Element wird der Eingabemenge entnommen
^ und zwischengespeichert.
[_ 3 | 5 1 4] Alle in der Ausgabemenge vorhandenen größeren
Elemente werden, vom Ende der Ausgabemenge beginnend,
um jeweils eine Stelle nach rechts verschoben.
Dabei wird das zwischengespeicherte Element in der
Eingabemenge überschrieben.
[2 3 | 5 1 4] Das zwischengespeicherte Element wird in das durch
die Verschiebung der Elemente in der Ausgabemenge
freigewordene Feld geschrieben.
-------------------------------------------------------------------------------
[2 3 | 5 1 4] Das nächste Element wird der Eingabemenge entnommen
^ und zwischengespeichert.
[2 3 _ | 1 4] Alle in der Ausgabemenge vorhandenen größeren
Elemente werden, vom Ende der Ausgabemenge beginnend,
um jeweils eine Stelle nach rechts verschoben.
Dabei wird das zwischengespeicherte Element in der
Eingabemenge überschrieben.
[2 3 5 | 1 4] Das zwischengespeicherte Element wird in das durch
die Verschiebung der Elemente in der Ausgabemenge
freigewordene Feld geschrieben.
-------------------------------------------------------------------------------
[2 3 5 | 1 4] Das nächste Element wird der Eingabemenge entnommen
^ und zwischengespeichert.
[_ 2 3 5 | 4] Alle in der Ausgabemenge vorhandenen größeren
Elemente werden, vom Ende der Ausgabemenge beginnend,
um jeweils eine Stelle nach rechts verschoben.
Dabei wird das zwischengespeicherte Element in der
Eingabemenge überschrieben.
[1 2 3 5 | 4] Das zwischengespeicherte Element wird in das durch
die Verschiebung der Elemente in der Ausgabemenge
freigewordene Feld geschrieben.
-------------------------------------------------------------------------------
[1 2 3 5 | 4] Das nächste Element wird der Eingabemenge entnommen
^ und zwischengespeichert.
[1 2 3 _ 5 |] Alle in der Ausgabemenge vorhandenen größeren
Elemente werden, vom Ende der Ausgabemenge beginnend,
um jeweils eine Stelle nach rechts verschoben.
Dabei wird das zwischengespeicherte Element in der
Eingabemenge überschrieben.
[1 2 3 4 5 |] Das zwischengespeicherte Element wird in das durch
die Verschiebung der Elemente in der Ausgabemenge
freigewordene Feld geschrieben.
-------------------------------------------------------------------------------
sortierte Ausgabemenge: [ 1 2 3 4 5 ]
[Bearbeiten] Komplexität
Die Anzahl der Vergleiche und Verschiebungen des Algorithmus ist von der Anordnung der Elemente in der unsortierten Eingangsmenge abhängig. Für den Average-Case ist eine Abschätzung der Laufzeit daher nicht so einfach möglich. Im Best Case ist die Komplexität jedoch linear (O(n)), d.h. sogar besser als bei den komplizierten Verfahren (QuickSort, MergeSort, HeapSort etc.). Im Worst Case dagegen quadratisch (O(n2)).
Wenn zur Bestimmung der richtigen Position eines Elementes die binäre Suche benutzt wird, kann man die Anzahl der Vergleiche, im Worst Case, durch log(n!) = nlogn − nloge + O(logn) = nlogn − 0,4426n + O(logn) abschätzen. Die Anzahl der Schiebeoperationen sind im Average-Case (n * (n − 1)) / 4 = O(n2).
Der Worst Case wäre ein absteigend sortiertes Array a, da wir bei jedem Element i die Methode move(i,0,a) aufrufen müssen. Die Anzahl der Schiebeoperationen beträgt in diesem Fall ((n * (n + 1)) / 2) − n = O(n2).
[Bearbeiten] Verwandter Sortieralgorithmus
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.
[Bearbeiten] Weblinks
- Java-Applet und Code zur Visualisierung
- http://www.inf.ethz.ch/~staerk/algorithms/SortAnimation.html Java Beispiele
- Weiteres Java-Applet zur Demonstration
Siehe auch: Liste von Algorithmen
