// Warum lieben Computer Ordnung? / Tipps zur Lösung
Insertion Sort: Fast wie Karten spielen!
Wie funktioniert der InsertionSort?
Die zweite Sortiermöglichkeit heisst InsertionSort. „Insertion“ ist Englisch und heisst auf Deutsch „Einfügen“.
Dieser Name kommt daher, weil der Computer die Zahl, die er gerade liest, am richtigen Ort in der
bereits sortierten Reihe oder Liste einfügen muss. In unserem Beispiel sind es CD-Titel,
die geordnet werden müssen.
InsertionSort funktioniert so:
- Der Computer bekommt die erste CD, die er ablegt.
- Dann bekommt er die zweite CD. Nun schaut er, ob der Titel der CD alphabetisch vor oder nach dem vorliegende CD-Titel ist. Wenn sie davor ist, so legt er die CD links neben die erste CD, sonst rechts davon.
- Bei allen folgenden CDs geht der Computer von links nach rechts vor
- Bei der dritten CD sucht er also von links ausgehend die Stelle, wo die neue CD in die schon sortierte Reihe einpasst.
- Danach startet er von neuem ganz links und wiederholt das ganze bis zur letzten sortierten CD. Immer wieder beginnt er von links, bis er keine CDs mehr hat.
Vielleicht tönt das jetzt ein bisschen kompliziert, aber wenn Sie sich an das Kartenspielen erinnern, wo Sie die Karten eine nach der andern aufnehmen, wird es ihnen bestimmt gleich klar. Diese Sortiermöglichkeit braucht viel weniger einzelne Schritte als BubbleSort, bis eine Reihe oder Liste sortiert ist. Dafür muss der Computer pro Schritt mehr machen als beim BubbleSort.
Andere Beispiele
Sie können sich diese Sortiermöglichkeit auch ansehen:
http://www.sorting-algorithms.com/insertion-sort