Insertion Sort: Fast wie Karten spielen!

Die zweite Sortiermöglichkeit heisst Insertion Sort. „Insertion“ ist Englisch und heisst auf Deutsch „Einfügen“. Dieser Name kommt daher, dass der Computer die Zahl, die er gerade liest, am richtigen Ort in der bereits sortierten Reihe einfügt. In unserem Beispiel sind es Karten, die geordnet werden müssen.

Wie funktioniert Insertion Sort?

1. Der Computer nimmt die erste Karte, die er in die Mitte legt.
2. Dann nimmt er die zweite Karte. Nun schaut er, ob die Karte gröser oder kleiner als die vorliegende Karte ist. Wenn sie kleiner ist, so legt er die Karte links neben die erste Karte, sonst rechts davon.
3. Bei allen folgenden Karten geht der Computer von links nach rechts vor
4. Bei der dritten Karte sucht er also von links her die Stelle, wo die neue Karte in die schon sortierte Liste passt.
5. Danach startet er von neuem ganz links und wiederholt das Ganze bis zur letzten sortierten Karte. Immer wieder beginnt er von links, bis er keine Karten mehr hat.

Vielleicht tönt das jetzt ein bisschen kompliziert. aber versuche dich ans Kartenspielen zu erinnern. Da nimmst du die Karten auch geordnet auf. Genau so funktioniert Insertion Sort.

So, nun bist du fit fürs Rätsel!

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