Der Sortieralgorithmus ,,Sortieren durch Einfügen`` - im Englischen InsertionSort genannt - ist der Sortieralgorithmus, den die meisten Menschen intuitiv benutzen, wenn sie bei Kartenspielen ihre Karten in der Hand sortieren: Die Karten werden der Reihe nach betrachtet und an der entsprechenden Position einsortiert.
Der InsertionSort-Algorithmus lässt sich folgendermaßen skizzieren:
Gegeben sei ein Array mit n Elementen, das in aufsteigender Reihenfolge sortiert werden soll. Die Elemente werden ab Index 1 der Reihe nach von links nach rechts betrachtet.
Das Array besteht also aus einem sortierten vorderen Teil, der in jedem Durchlauf um ein Element wächst, und einem unsortierten hinteren Teil, der entsprechend schrumpft. Betrachtet wird in jedem Durchlauf das erste Element des unsortierten Teils, das in den bereits sortierten Teil einsortiert wird.
Die folgende Klasse InsertionSort (InsertionSort.ham) implementiert das Interface SortierAlgorithmus entsprechend des InsertionSort-Algorithmus:
public class InsertionSort implements SortierAlgorithmus {
// sortiert das uebergebene Array in aufsteigender Reihenfolge
// gemaess dem InsertionSort-Algorithmus
public void sortiere(int[] zahlen) {
// durchlaufe alle Zahlen ab der zweiten
for (int aktIndex=1; aktIndex<zahlen.length; aktIndex++) {
int aktuelleZahl = zahlen[aktIndex];
int einfuegeIndex = sucheEinfuegeIndex(zahlen, aktuelleZahl, aktIndex);
zahlen[einfuegeIndex] = aktuelleZahl;
}
}
// sucht und liefert den Index des Arrays, wo
// die aktuelle Zahl eingefuegt werden muss, und verschiebt alle
// größeren Zahlen jeweils um eine Position nach hinten im Array
private int sucheEinfuegeIndex(int[] zahlen, int zahl, int aktIndex) {
int vergleichsIndex = aktIndex-1;
while (vergleichsIndex >= 0 && zahlen[vergleichsIndex] > zahl) {
// Zahl im Array um eine Position nach hinten verschieben
zahlen[vergleichsIndex+1] = zahlen[vergleichsIndex];
vergleichsIndex--;
}
return vergleichsIndex+1;
}
/* der InsertionSort-Algorithmus in kompakter Form
public void sortiere(int[] zahlen) {
for (int aktIndex=1; aktIndex<zahlen.length; aktIndex++) {
int aktuelleZahl = zahlen[aktIndex];
int vergleichsIndex = aktIndex-1;
while (vergleichsIndex >= 0 && zahlen[vergleichsIndex] > aktuelleZahl) {
zahlen[vergleichsIndex+1] = zahlen[vergleichsIndex];
vergleichsIndex--;
}
zahlen[vergleichsIndex+1] = aktuelleZahl;
}
}
*/
}
Die folgende Hamster-Klasse InsertionSortHamster (InsertionSortHamster.ham) implementiert das Interface SortierHamster und visualisiert dabei den InsertionSort-Algorithmus. Voraussetzung ist, dass es im Territorium zwei nicht durch Mauern blockierte Reihen unterhalb des Standard-Hamsters gibt. In der ersten Reihe unterhalb der Körnerhaufenreihe markiert ein Markierungshamster (grüner Hamster) jeweils den Körnerhaufen, der in den sortierten Teil einsortiert werden soll. Ein Körnerhaufensortierhamster als Vertretungshamster des Standard-Hamsters (roter Hamster) deponiert in jedem Durchlauf zunächst den betrachteten Körnerhaufen um zwei Reihen nach unten. Anschließend sucht er im linken Teil den Einfügeindex und verschiebt dabei unter Umständen größere Körnerhaufen nach rechts. Hat er den Einfügeindex gefunden, holt er die deponierten Körner und legt sie auf der entsprechenden Kachel ab.
// Demonstration des InsertionSort-Algorithmus
public class InsertionSortHamster
extends KoernerHaufenSortierHamster
implements SortierHamster
{
private MarkierungsHamster aktIndexHamster = null;
// markiert den aktuell betrachteten Koernerhaufen
private int anzahlKoernerHaufen = 0;
// Anzahl der zu sortierenden Koernerhaufen
private int anzahlDeponierteKoerner = 0;
// Koerneranzahl des aktuellen Koernerhaufens
// Konstruktor
public InsertionSortHamster(boolean mitErlaeuterungen) {
super(mitErlaeuterungen);
this.erlaeuterung(
"Ich sortiere die Koernerhaufen auf der Basis des " +
"InsertionSort-Algorithmus.");
this.aktIndexHamster =
new MarkierungsHamster(this.getReihe() + 1, this.getSpalte(),
this.getReihe(), mitErlaeuterungen);
this.aktIndexHamster.erlaeuterung(
"Ich markiere jeweils den Koernerhaufen,\n" +
"der an der richtigen Position eingefuegt werden soll.");
this.anzahlDeponierteKoerner = 0;
}
// Der Standard-Hamster steht mit Blickrichtung OST irgendwo im Territorium.
// Ein Vertretungshamster soll die Koernerhaufen bis zur nächsten Wand in
// aufsteigender Reihenfolge sortieren.
// Voraussetzung: Unterhalb des Standard-Hamsters existieren zwei nicht
// durch Mauern blockierte Reihen.
public void sortiereKoernerHaufen() {
this.erlaeuterung(
"Ich zaehle nun die Anzahl der zu sortierenden Koernerhaufen.");
this.anzahlKoernerHaufen = ermittleAnzahlKoernerHaufen();
this.erlaeuterung(
"Die Anzahl der zu sortierenden Koernerhaufen betraegt " +
this.anzahlKoernerHaufen +
",\nd.h. die Indizes der Haufen liegen zwischen 0 und " +
(this.anzahlKoernerHaufen-1) +
".");
// durchlaufe die Menge der Koernerhaufen von links nach rechts;
// merke dir den aktuellen Koernerhaufen
for (int aktIndex = 1; aktIndex < this.anzahlKoernerHaufen; aktIndex++) {
this.aktIndexHamster.markiereIndex(aktIndex);
this.erlaeuterung(
"Ich suche nun den Einfuegeindex des " +
"markierten Koernerhaufens bei Index " +
this.aktIndexHamster.liefereIndex() +
".\nDazu deponiere ich zunaechst die " +
this.aktIndexHamster.liefereAnzahlKoerner() +
" Koerner des markierten Koernerhaufens.");
this.deponiereKoerner();
this.erlaeuterung(
"Ich suche nun zwischen den Indizes 0 und " +
(aktIndex-1) +
" den ersten Koernerhaufen von rechts,\n" +
" der weniger oder gleich " +
this.anzahlDeponierteKoerner +
" Koerner besitzt.\n" +
"Rechts von diesem befindet sich der Einfuegeindex.\n" +
"Groessere Haufen verschiebe ich dabei jeweils " +
"um einen Index nach rechts.");
int einfuegeIndex = this.sucheEinfuegeIndex();
this.erlaeuterung(
"Einfuegeindex gefunden. Er liegt bei Index " +
einfuegeIndex +
".\nIch hole nun die deponierten Koerner und lege sie hier ab.");
this.fuegeDeponierteKoernerEin(einfuegeIndex);
}
this.beendeSortierung();
}
private void deponiereKoerner() {
// die Koerner werden zwei Reihen darunter deponiert
this.laufeZuIndex(this.aktIndexHamster.liefereIndex());
this.anzahlDeponierteKoerner = this.nimmAlle();
this.setzeBlickrichtung(Hamster.SUED);
this.vor(2);
this.gib(this.anzahlDeponierteKoerner);
this.kehrt();
this.vor(2);
this.linksUm();
}
private int sucheEinfuegeIndex() {
// sucht und liefert den Index der Koernerhaufen, wo
// der aktuelle Koernerhaufen - sprich die deponierten Koerner -
// eingefuegt werden muss, und verschiebt alle
// größeren Koernerhaufen jeweils um eine Position nach rechts
this.vor();
while (this.liefereIndex() >= 0 &&
this.liefereAnzahlKoerner() > this.anzahlDeponierteKoerner) {
int anzahl = this.nimmAlle();
this.kehrt();
this.vor();
this.gib(anzahl);
this.kehrt();
this.vor();
this.vor();
}
return this.liefereIndex()+1;
}
private void fuegeDeponierteKoernerEin(int index) {
// holt die deponierten Koerner und fuegt sie an der uebergebenen
// Position in die Menge der Koernerhaufen ein
this.laufeZuKachel(this.getReihe() + 2, this.aktIndexHamster.getSpalte());
int anzahl = this.nimmAlle();
this.laufeZuKachel(this.getReihe() - 2, this.startSpalte + index + 1);
this.gib(anzahl);
}
private void beendeSortierung() {
this.laufeZuSpalte(this.startSpalte);
this.setzeBlickrichtung(Hamster.OST);
this.erlaeuterung("Sortierung erfolgreich beendet!");
}
}
Mit dem folgendem objektorientierten Hamster-Programm (SortierenMitInsertionSort) (SortierenMitInsertionSort.ham) können Sie sich von den Hamstern den InsertionSort-Algorithmus demonstrieren lassen.
void main() {
Hamster paul = Hamster.getStandardHamster();
String antwort =
Hamster.getStandardHamster().liesZeichenkette(
"Moechten Sie textuelle Erlaeuterungen (ja/nein)?");
SortierHamster sortierer = new InsertionSortHamster(antwort.equals("ja"));
sortierer.sortiereKoernerHaufen();
}
Der InsertionSort-Algorithmus ist stabil und arbeitet in-place.
Sei n die Anzahl an zu sortierenden Elementen. Die Anzahl an Vergleichen zwischen den Array-Elementen beträgt
, wenn das Array bereits aufsteigend sortiert ist,
, wenn das Array absteigend sortiert ist,
, wenn die Anordnung der Elemente im Array zufällig ist.
Die Anzahl an ,,halben Vertauschungen`` (Bewegungen) von Array-Elementen beträgt
, wenn das Array bereits aufsteigend sortiert ist,
, wenn das Array absteigend sortiert ist,
, wenn die Anordnung der Elemente im Array zufällig ist.
Im Web finden sich zahlreiche weitere Informationen zum InsertionSort-Algorithmus, z.B. unter