Home

Einheiten

Suchen und Sortieren gehört zu den algorithmischen Grundaufgaben. In beiden Blöcken sollen die Jugendlichen erkennen, dass zwischen Datenstruktur und Algorithmus, oder in der Sprache des Alltagslebens, zwischen Problemaufbereitung und Problemlösung, ein enger Zusammenhang besteht. Umso besser man ein Problem aufbereitet, umso rascher erzielt man die Lösung für einen konkreten Fall.

Abgesehen von diesem gemeinsamen Prinzip, das auch dazu führt, dass Sortieren mitunter die Vorstufe für einfaches Suchen ist, treten Sortierprobleme auch jenseits der Informatik in vielen Lebensbereichen auf. Diesen nicht nur naiv sondern mit dem Wissen anzuwenden, dass es unterschiedliche Sortieralgorithmen gibt, jeder mit seiner spezifischen Stärke und Schwäche, kann viel Zeit und Mühsal ersparen.

Wir beginnen die Sortiereinheit daher mit elementaren, unmittelbar einsichtigen Sortieralgorithmen wie Bubblesort, Insertion-Sort und Selection-Sort. Dazu kontrastierend kann man mit Merge-Sort oder Quicksort zeigen, dass sich nachdenken über die Problemstruktur lohnt.
Da wir nicht nur nachvollziehen wollen, wie ein Computer sortiert, zeigen wir mit Radixsort ein Verfahren, das für Menschen, die ja nicht auf Binärentscheidungen eingeschränkt sind, eine sehr effiziente Lösung darstellt.
Die Komplexitätsabschätzungen bieten Querbeziehungen zu Mathematik. Die effizienten Verfahren lassen auch einen Blick zur Rekursion (Modul P5) wünschenswert erscheinen.