Insertion Sort: Fast wie Karten spielen!

Wie funktioniert der Insertion Sort?

Die zweite Sortiermöglichkeit heisst Insertion Sort. „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 einfügen muss. In unserem Beispiel sind es nummerierte CDs, die geordnet werden müssen.

Insertion Sort funktioniert so:

1. Der Computer bekommt die erste CD, die er in die Mitte legt.
2. Dann bekommt er die zweite CD. Nun schaut er, ob die Nummer der CD gröser oder kleiner als die vorliegende CD-Nummer ist. Wenn sie kleiner ist, so legt er die CD links neben die erste CD, sonst rechts davon.
3. Bei allen folgenden CDs geht der Computer von links nach rechts vor
4. Bei der dritten CD sucht er also von links ausgehend die Stelle, wo die neue CD in die schon sortierter Reihe einpasst.
5. 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 du dich ans Kartenspielen erinnerst, wo du die Karten geordnet aufnimmst, wird es dir bestimmt gleich klar. Diese Sortiermöglichkeit braucht viel weniger einzelne Schritte als BubbleSort, bis eine Liste sortiert ist. Dafür muss der Computer pro Schritt mehr machen als beim BubbleSort.

Andere Beispiele

Du kannst dir diese Sortiermöglichkeit auch ansehen: http://www.sorting-algorithms.com/insertion-sort

Weiter mit: Wie Computer sortieren?

< Zurück | Weiter >
<  Zur Übersicht  >