Beispielaufgabe „Sortierrutschen“ (Kalender 7-9, 2014)
Haben die Packwichtel alle Geschenke für eine Familie fertig verpackt, legen sie diese in einen Sack. Die schweren Geschenke legen sie nach unten, damit sie die leichteren Geschenke nicht zerdrücken. Um diese Arbeit zu beschleunigen entwickeln Tüftelwichte Wendel und Packwichtel Ada gerade eine Maschine. In der Testversion sollen damit vier Geschenke nach ihrem Gewicht sortiert werden.
Die Maschine soll aus mehreren Rutschen und „wiegenden Kreuzungen“ bestehen: Oben werden vier Geschenke hineingeworfen. Kommt eines an einer Kreuzung an, bleibt es dort liegen, bis ein zweites ankommt. Beide Geschenke werden dann gewogen. Das leichtere Geschenk wird immer nach links, das schwerere nach rechts weiter geschickt, bis alle Geschenke unten ankommen.
Wendel und Ada sind noch unsicher, wie die Rutschen angeordnet sein müssen, damit die Geschenke nach dem Gewicht sortiert unten ankommen. Deswegen haben sie vier Testmaschinen gebaut:
Fredi (39 kg), Oswald (34 kg), Iphis (28 kg) und Esmeralda (21 kg) sollen die Maschine testen und oben in die Rutschen springen. Ada schickt sie in zwei Reihenfolgen in die Rutschmaschine:
1.) Iphis – Esmeralda – Fredi – Oswald
2.) Oswald – Fredi –Esmeralda – Iphis
Bei welcher der vier Rutschmaschinen kommen die vier Wichtel in beiden Durchgängen dem Gewicht nach sortiert unten an?
- a)
- Maschine 1
- b)
- Maschine 2
- c)
- Maschine 3
- d)
- Maschine 4
Diese Aufgabe wurde vorgeschlagen von:
Das „Informatik–Biber“–Team
Bundesweite Informatikwettbewerbe
https://bwinf.de/informatik-biber/
Lösung:
Antwortmöglichkeit d) ist richtig: Nur die Maschine 4 sortiert die Wichtel in beiden Durchgängen richtig nach dem Gewicht.
Um die richtige Lösung zu ermitteln, musst du die beiden Durchgänge für die Rutschmaschinen durchprobieren. Dabei können dir Diagramme, wie unten zu sehen, helfen. Die Zeichnungen werden übersichtlicher, wenn du statt der Wichtelnamen ihre Gewichte verwendest. Es gibt zwei verschiedene Lösungswege, je nachdem ob du die leichten Pakete in der Draufsicht nach links weiterschickst (siehe erste Lösungsskizze) oder ob du dich in die Geschenke hineinversetzt und sie in „Fahrtrichtung“ nach links weiterleitest. Dann werden sie in der Draufsicht nach rechts weitergeleitet. In beiden Fällen ist aber nur die Maschine 4die richtige Lösung.
Durchgang 1:
Die Ausgangsreihenfolge der Gewichte im ersten Durchgang ist:
28–21–39–34
Was in den vier Testmaschinen im ersten Durchgang passiert, siehst du in den folgenden Diagrammen. Dabei werden die vier Zahlen, die für die vier Gewichte stehen, jeweils die Pfeile entlanggeschickt. Die roten Felder sind die Startfelder. In den weißen Feldern treffen jeweils zwei Wichtel aufeinander und werden gewogen. Der leichtere Wichtel, also die kleinere Zahl, wird dann nach links weitergeschickt. Der schwerere Wichtel, also die größere Zahl, wird nach rechts geschickt. In den grünen Feldern siehst du jeweils das Ergebnis. Die rot umrandeten Ergebnisse sind falsch.
 |
 |
 |
 |
In den Testmaschinen 1 und 4 werden die vier Wichtel im ersten Durchgang korrekt nach ihrem Gewicht sortiert. Die anderen beiden Testmaschinen 2 und 3 liefern bereits ein falsches Ergebnis. Daher brauchst du für den zweiten Durchgang nur noch die beiden Maschinen 1 und 4 zu prüfen.
Durchgang 2:
Die Ausgangsreihenfolge im ersten Durchgang ist:
34–39–21–28
Was in den Testmaschinen 1 und 4 im zweiten Durchgang passiert, siehst du in den folgenden Diagrammen:
 |
 |
Die Testmaschine 1 sortiert die Wichtel in diesem zweiten Durchgang nicht korrekt nach dem Gewicht. Maschine 4 sortiert hingegen auch in diesem Durchgang richtig. Damit stimmt die Antwortmöglichkeit d), nur die Maschine 4 sortiert die Wichtel in beiden Durchgängen(und übrigens auch in allen möglichen Kombinationen) richtig nach dem Gewicht.
Alternativer Lösungsweg:
Schickst du die leichteren Wichtel in „Fahrtrichtung“ nach links weiter, sieht der erste Durchgang für Maschine 1 so aus:
Du kannst auch die anderen Diagramme erstellen. Die einzelnen Durchgänge geben unterschiedliche Lösungen als oben. Vor allem ist die Sortierung hier von schwer nach leicht. Trotzdem bleibt das Ergebnis dasselbe: Nur Maschine 4 sortiert richtig. Das liegt daran, dass alle Maschinen symmetrisch sind. Sie sehen genauso aus, wenn du sie entlang der langen Kante „von links auf rechts“ umdrehst.
Blick über den Tellerrand
Die Rutschmaschine aus der Aufgabe ist ein sogenannter Algorithmus. Ein Algorithmus ist eine systematische Vorgehensweise, mit der ein bestimmtes Problem gelöst werdensoll. Er ist also eine feste, immer gleiche Handlungsvorschrift. Algorithmen benutzt du auch selbst, beispielsweise dann, wenn du große Zahlen schriftlich addierst oder subtrahierst.
Zu jedem Algorithmus gehören ein Input und ein Output. Der Input sind die Werte, die an den Algorithmus übergeben werden und der Output die Werte, die er am Ende ausgibt. Im Falle dieser Aufgabe sind die Startplätze der Wichtel der Input und die sortierten Wichtel am Ende der Output.
In der Informatik werden Algorithmen (Plural von Algorithmus) vor allem gebraucht, um komplexe Aufgaben am Computer zu lösen. Bei der Programmierung wird der Algorithmus in kleine Schritte aufgeteilt, sodass der Computer ihn Schritt für Schritt ausführen kann. Wichtig ist dabei, dass jeder Algorithmus bestimmte Eigenschaften erfüllen muss. Aus praktischen Gründen muss er in endlich vielen Schritten ausführbar sein. Zudem muss jeder Schritt des Algorithmus eindeutig sein, da ein Computer nur den Anweisungen des Algorithmus folgt und nicht zu Interpretationen fähig ist.
In den Rutschmaschinen werden immer wieder gleichzeitig mehrere Paare von Wichteln miteinander verglichen. Deshalb nennt man einen solchen Algorithmus auch einen parallelen Algorithmus. Im Gegensatz dazu stehen die sequentiellen Algorithmen, bei denen Aktivitäten nur hintereinander stattfinden. Mit parallelen Algorithmen kann also Zeit gespart werden.
Das Sortieren von Elementen ist eines der am häufigsten vorkommenden Probleme, die mit einem Computer gelöst werden. Dementsprechend gibt es viele Sortieralgorithmen, die auf verschiedenen Ansätzen basieren. Da Zeit ein wichtiger Faktor beim Lösen von Problemen am Computer ist, beschäftigen sich viele Informatiker_innen damit, Sortiervorgänge zu beschleunigen, damit sie möglichst schnell durchgeführt werden können. Während im Fall der Rutschmaschine immer zwei Wichtel miteinander verglichen werden, gibt es auch Ansätze, die ohne den direkten Vergleich von Elementen auskommen. Diese nennt man nicht vergleichsbasiertes Sortieren.
