 | Themen |
|
InsertionSort
InsertionSort (engl. insertion - Einfügen) ist ein einfaches
Sortierverfahren, das zwar weit weniger effizient als andere anspruchsvollere
Verfahren ist, jedoch folgende Vorteile bietet:
-
einfach zu implementieren
-
effizient bei (ziemlich) kleinen Eingabemengen
-
effizient bei Eingabemengen, die schon weitgehend sortiert sind
-
stabil (d.h., die Reihenfolge von schon sortierten Elementen ändert sich nicht)
-
minimaler Speicherverbrauch
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. Das Verfahren arbeitet also in-place. Geht man in der
Reihenfolge der ursprünglichen Menge vor, so ist es jedoch (etwa im Gegensatz
zu SelectionSort) 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 (siehe eigenes Kapitel) vergleichsweise
effizient erfolgen kann.
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 ]
Implementation
/**
* INSERTIONSORT
* hier implementiert zur Sortierung eines int-Arrays.
* Der Reihe nach werden die Elmente des zu sortierenden
Arrays in das bereits
* sortierte Teilarray eingefügt. Dabei wird die passende
Einfügeposition
* jeweils per binsearch() ermittelt. Vor dem Einfügen
müssen die schon sortierten Zahlen,
* die größer sind als die einzufügende Zahl, noch um eine
Array-Position nach
* rechts verschoben werden.
*
* @param a int-Array, das sortiert werden soll
*/
public static void insertionSort(int[] a){
int value; // Zwischenspeicher für das nächste
einzufügende (aktuelle) Element
int index; // Einfügeposition, jeweils ermittelt per
binsearch()
for(int i=1; i<a.length; i++){
// das erste Element (Index 0) stellt eine
ein-elementige, sortierte Teilfolge dar
value = a[i];
// Einfügeposition finden, sortierte Teilfolge geht
jeweils von Index 0..i-1
index = binsearch(a,value,0,i-1);
// Verschieben der Elemente rechts von der
Einfügeposition um eine Position nach rechts
for(int k=i-1; k>=index; k--){
a[k+1] = a[k];
}
// Einfügen des aktuellen Elementes
a[index] = value;
}
}
» drucken: pdf | html
|
JavaHamster
Java
Binäre Suche
