Die unsortierte Top-10
Lösung geprüft
Die Aufgabe der heutigen Stunde ist die unsortierte Top-10! Zehn Albumcover liegen durcheinander und sollen wieder in die richtige Reihenfolge – aber nach festen Regeln. Das ist die Aufgabe, mit der die ganze Sortier-Einheit anfängt, und sie kommt bewusst ohne Rechner aus.
Das war mal das Ranking der am meisten verkauften Alben der Welt. Die Alben unten sind durcheinander geraten und sollen wieder in die richtige obige Reihenfolge gebracht werden.
- Überlegen Sie sich eine eindeutige Handlungsvorschrift (Algorithmus), um die Platten (möglichst schnell) zu sortieren.
- Nur zwei Alben-Rankings dürfen pro Schritt verglichen und ggf. vertauscht werden.
- Es darf in jedem Sortier-Schritt immer nur die gleiche Regel angewendet werden.
- Ein Schritt ist die Wiederholung der Handlungsvorschrift.
- Notieren Sie sich die Handlungsvorschrift in Stichpunkten.
Worauf die Regeln hinauslaufen
Die drei Einschränkungen sind der eigentliche Inhalt der Aufgabe. Sie verbieten nämlich genau das, was man intuitiv machen würde – nämlich alle zehn Cover gleichzeitig anschauen und sie in einem Rutsch hinlegen.
| Regel | Was sie erzwingt |
|---|---|
| Nur zwei pro Schritt vergleichen | Ein Computer kann auch nur zwei Werte auf einmal vergleichen. Du musst wie eine Maschine arbeiten. |
| Immer dieselbe Regel | Ein Algorithmus ist eine feste Vorschrift, keine Sammlung von Bauchentscheidungen. |
| Eindeutig | Zwei Leute mit derselben Vorschrift müssen bei denselben Schritten landen. |
Meine Handlungsvorschrift
Ich nehme das Verfahren, auf das die meisten von selbst kommen – nämlich Selection Sort, auch wenn es in der Stunde noch nicht so heißt:
- Schau dir alle Alben an, die noch nicht einsortiert sind.
- Merke dir das erste davon als „bisher bestes".
- Vergleiche es mit dem nächsten. Hat das nächste ein besseres Ranking, merke dir dieses als „bisher bestes".
- Wiederhole Schritt 3, bis du alle unsortierten durch hast.
- Lege das gemerkte Album ans Ende der sortierten Reihe.
- Ist noch etwas übrig, fang wieder bei Schritt 1 an.
Diese Vorschrift erfüllt alle drei Vorgaben: in Schritt 3 werden immer genau zwei verglichen, die Regel ist in jedem Durchlauf dieselbe, und sie ist eindeutig – zwei Leute kommen zum selben Ergebnis.
Wie lange das dauert
Beim ersten Durchlauf vergleicht man 9-mal (das erste mit allen anderen), beim zweiten 8-mal, dann 7-mal und so weiter:
9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 VergleicheAllgemein bei n Alben: n · (n-1) / 2. Bei 10 sind das 45,
bei 100 schon 4 950. Verzehnfacht man die Menge, wird es ungefähr
hundertmal so aufwendig – das ist genau die O(n²), über die später
gesprochen wird.
Andere Vorschriften, die genauso gültig sind
Die Aufgabe verlangt nicht dieses eine Verfahren. Zwei andere, die die Regeln ebenso erfüllen:
| Vorschrift | Wie sie sich anfühlt |
|---|---|
| Einfügen: Nimm das nächste Album und schiebe es in der schon sortierten Reihe so weit nach links, bis das Album links davon besser platziert ist. | So sortieren die meisten Leute Spielkarten auf der Hand. Das ist Insertion Sort. |
| Nachbarn tauschen: Geh die Reihe von links nach rechts durch und tausche je zwei Nachbarn, wenn sie falsch herum liegen. Wiederhole, bis kein Tausch mehr nötig war. | Sehr einfach zu befolgen, dauert aber am längsten. Das ist Bubble Sort. |
Wichtig für die Bewertung ist nicht, welches Verfahren du nimmst, sondern ob deine Beschreibung eindeutig ist. Sätze wie „dann sortiere ich den Rest" sind keine Handlungsvorschrift – das ist genau das, was noch beschrieben werden soll.
Der häufigste Fehler
Viele schreiben als ersten Punkt „ich suche das Album mit Platz 1 und lege es nach vorne". Das klingt richtig, verstößt aber gegen die erste Regel: um es zu finden, hast du alle zehn gleichzeitig angeschaut. Ein Computer kann das nicht. Deshalb muss die Vorschrift ausdrücklich beschreiben, wie man das Minimum durch Zweiervergleiche findet – und genau das machen die Schritte 2 bis 4.