Einführung

In Programmen zur Medienwiedergaben, aber auch im Datei-Explorer besteht die Möglichkeit, sich die enthaltenden Elemente nach unterschiedlichen Kriterien sortiert anzeigen zu lassen. Der Benutzer kann dabei in der Regel sogar zwischen auf- und absteigender Reihenfolge wählen. Die folgende Abbildung zeigt die Musikstücke in einer Wiedergabesoftware, wobei eine aufsteigende Sortierung nach dem Kriterium „Künstler“ gewählt wurde.

Wünscht der Nutzer nun eine andere Sortierung, müssen die enthaltenen Elemente neu sortiert werden. – Ein Computer benötigt dafür, auch bei mehreren tausend Musikstücken, nicht mehr, als den Bruchteil einer Sekunde. Doch haben Sie sich schon einmal gefragt, wie der Computer das eigentlich schafft?

In dieser Erinführung wollen wir das Problem des Sortierens zunächst ganz praktisch untersuchen. Fertigen Sie zunächst einen Ausdruck der Sortierkarten an und schneiden Sie diese aus. Die Karten sollten Sie auch nach Bearbeitung der Aufgabe aufbewahren, da sie Ihnen im weiteren Unterrichtsverlauf eine gute Hilfe sein können.

Erkundung 1 (Partnerarbeit)

Wählen Sie 10-12 Sortierkarten aus. Mischen Sie die Karten und legen Sie die Karten verdeckt vor sich in eine Reihe. Die vor Ihnen liegenden Karten sollen im Folgenden nach dem Titel des Songs aufsteigend sortiert werden soll. Folgende Regeln, die in etwa den Möglichkeiten eines Computers entsprechen, sind dabei zu beachten:

• es dürfen zeitgleich höchstens zwei Karten aufgedeckt werden
• nur die Inhalte der aufgedeckten Karten können miteinander verglichen werden
• nur eine Karte darf aus der Reihe genommen und "zwischengespeichert" werden
• Karten können nur in den Zwischenspeicher oder auf ein leeres Feld verschoben werden

Entwickeln Sie eine Strategie, um die Karten systematisch zu sortieren. Verschriftlichen Sie Ihren Algorithmus soweit, dass er auch von anderen Personen ausgeführt werden kann.

Geben Sie Ihren Algorithmus zur Überprüfung an zwei Mitschüler weiter – untersuchen Sie zeitgleich den Ansatz Ihrer Mitschüler.

Erkundung 2 (Partnerpuzzle)

In den folgenden Videos werden zwei bekannte Sortierfahren dargestellt:

• Insertion Sort (Sortieren durch Einfügen)

   

• Selection Sort (Sortieren durch Auswählen)

Schauen Sie sich zusammen mit Ihrem Partner eines der beiden Videos an. Versetzen Sie sich in die Lage, das dargestellte Verfahren mit Hilfe Ihrer Sortierkarten selbst durchzuführen.

Suchen Sie sich eine(n) neuen Partner(in), der/die sich zuvor mit dem anderen Verfahren befasst hat. Stellen Sie sich die Sortierfahren gegenseitig vor. Diskutieren Sie Gemeinsamkeiten und Unterschiede beider Verfahren.