Aktivität 7 – Sortieralgorithmen

Vom Leichtesten zum Schwersten – Sortieralgorithmen

Häufig verwendet man Computer dazu, Listen von Elementen in eine bestimmte Ordnung zu bringen. So kann man beispielsweise Namen alphabetisch sortieren, Verabredungen nach Datum, oder Zahlen in auf- oder absteigender Reihenfolge sortieren. Wir interessieren uns dafür wie man Elemente sortiert, um Elemente beim Suchen einfacher finden zu können. Zudem ist das Aufspüren spezieller Werte (wie beispielsweise das größte oder kleinste Element) nach dem Sortieren ganz einfach. Wenn man beispielsweise die Noten einer Klasse aufsteigend sortiert, ist es einfach die höchste und die tiefste Note zu finden; diese findet man am Anfang beziehungsweise am Ende der sortierten Liste.

Allerdings erhalten wir die Ordnung nicht gratis; wir zahlen dafür mit Zeit. Es gibt diverse Methoden, die verschieden lange dauern. Sie alle haben den gleichen Effekt: Sie sortieren die Elemente. Da dies jedoch bei den verschiedenen Methoden nicht gleich lange dauert, sind wir daran interessiert, die beste Methode zu finden. Wählt man die falsche, kann es unter Umständen sehr lange dauern bis alle Zahlen korrekt angeordnet sind, und das auch auf einem schnellen Computer.

In dieser Aktivität sollen Kinder verschiedene Sortierverfahren kennenlernen und deren Geschwindigkeit vergleichen.

- Mathematik: Wiegen, Zählen, Vergleichen

- Informatik: Algorithmen

- Wie benutzt man eine Waage

- Was heißt es, Elemente zu ordnen

- Wie vergleicht man Zahlen

- 8+

Worum geht es in dieser Aktivität?

Es ist wesentlich einfacher Informationen in einer geordneten Liste zu finden, als wenn man sie in einer ungeordneten Liste suchen müsste. Telefonbücher, Wörterbücher und Verzeichnisse sind alphabetisch geordnet und das Leben wäre wesentlich weniger bequem, wenn sie es nicht wären. Wenn eine Liste von Zahlen (wie zum Beispiel eine Liste mit Ausgaben) geordnet vorliegt, ist es einfach die Extremen zu sehen, weil sie sich ganz am Anfang oder ganz am Schluss der Liste befinden, während sie in unsortierten Listen überall vorkommen können. Auch doppelte Einträge findet man einfach, da diese in sortierten Listen direkt nebeneinander liegen.

Computer verbringen einen großen Teil der Zeit damit, Dinge zu ordnen. Also ist es für InformatikerInnen von Interesse dies schnell und gut zu machen. Einige der langsameren Methoden, wie beispielsweise Sortieren durch Einfügen, Sortieren durch Auswählen oder Bubblesort, können in gewissen Situationen sehr nützlich sein, doch in den meisten Fällen verwendet man ein schnelles Verfahren, wie zum Beispiel Quicksort.

Quicksort verwendet ein Konzept, das man Rekursion nennt. Das bedeutet, dass wir die Liste immer wieder in kleinere Teile unterteilen und auf diesen kleineren Teilen genau dasselbe tun wie wir es vorher beim größeren Teil gemacht haben. Diesen Ansatz im Speziellen nennt man ,Teile und Herrsche’. Die Liste wird immer wieder unterteilt, bis wir schließlich fähig sind (wenn die Liste klein genug ist) deren Ordnung zu bestimmen. Im Falle von Quicksort werden die Listen unterteilt bis sie nur noch ein Element enthalten, da es einfach ist eine Menge mit nur einem Element zu sortieren. Das klingt zwar kompliziert, verhilft uns aber in der Praxis dazu, wesentlich schneller zum Ziel zu kommen als mit anderen Methoden.

Übungen und Materialien

Materialien

- 8 Behälter, alle gleich groß, aber verschieden schwer

- Eine Waage

- Arbeitsblatt: Gewichte sortieren (Seite 81)

- Arbeitsblatt: Teilen und Herrschen (Seite 82)