Robot Karol: Ziegelstapel der Höhe nach sortieren

>>> zurück zur Übersicht von Robot Karol

unsortierte Reihe

sortierte Reihe

Es gehört zu den wichtigsten und am häufigsten gestellten Aufgaben, irgendwelche Objekte zu sortieren. Da man oft große Datenmassen sortieren muss, ist es auch äußerst wichtig, möglichst schnelle Sortiermethoden zu entwickeln. Dabei ist für die Geschwindigkeit natürlich entscheidend, was der Sortierer alles kann. Und da sind wir beim Knackpunkt.

Karol kann recht wenig.

1. Karol kann sich zum Beispiel nichts merken (alles, was er früher schon einmal angeschaut hat, muss er immer wieder anschauen)
2. Karol kennt keine Zahlen, kann keine Zahlen vergleichen.
3. Karol kennt nur seine unmittelbare Nachbarschaft.

... und so wird eine einfache Sortieraufgabe zu einer knackige Sache!

1. Sortieridee

Wenn Karol an der unsortierten Ziegelstapelreihe (von rechts nach links) vorbei läuft, kann er nur benachbarte Stapelhöhen vergleichen. Karol sieht nicht - wie Du - "auf einen Blick" den kleinsten Stapel! Also wird er an der Stapelreihe vorbeigehen und immer nur benachbarte Stapel richten, also vertauschen, wenn sie in falscher Ordnung stehen.

Dann wandert aber nur der kleinste Stapel ganz nach Süden bei einem Durchlauf. Also muss er mehrmals an allen vorbei. Beim zweiten Durchlauf werden schon die beiden kleinsten Stapel im Süden in richtiger Folge stehen, u.s.w..

Und auch, um zwei benachbarte Stapel zu vergleichen, muss Karol Ziegel abtragen, bis einer der beiden Stapel leer ist und dann sehen, was wo übrig bleibt, denn Karol kann keine Zahlen vergleichen. ... also lass uns ganz am Anfang beginnen:

2. Einfache neue Bewegungsanweisungen

Da wir sehr häufig einen Sidestep links oder rechts (immer wieder) brauchen, wollen wir folgende neuen Anweisungen vereinbaren:

Anweisung LinksGehen 
  LinksDrehen Schritt RechtsDrehen 
*Anweisung

Anweisung RechtsGehen 
  RechtsDrehen Schritt LinksDrehen  
*Anweisung

3. Vergleichen zweier Stapel

Um zwei Stapel zu vergleichen, vor denen Karol steht, bleibt ihm nichts anderes übrig, als von beiden Stapeln gleich viele Ziegel abtragen, bis einer der beiden Stapel leer ist. Dann weiß er: auf dem leeren Platz war zuvor der kleinere Stapel. Karol kann die abgetragenen Ziegel hinter sich parken. Das macht die folgende Anweisung:

Anweisung gleicheweglegen
//Karol steht vor zwei Stapeln und überprüft den vorliegenden und den linken Stapel
//Solange beide Stapel Ziegel bergen, legt er von jedem Stapel einen Ziegel hinter sich
//Am Ende ist einer der beiden Reststapel leer
//Karol steht am Ende immer am rechten Stapel
 MarkeSetzen
 solange IstMarke tue
    wenn NichtIstZiegel dann MarkeLöschen *wenn
    LinksGehen
    wenn NichtIstZiegel dann
       RechtsGehen MarkeLöschen
    sonst
       RechtsGehen
    *wenn
    wenn IstMarke dann
       Aufheben LinksDrehen LinksDrehen Hinlegen
       RechtsDrehen Schritt RechtsDrehen
       Aufheben LinksDrehen LinksDrehen Hinlegen
       LinksDrehen Schritt LinksDrehen
    *wenn
 *solange
*Anweisung

4. Evtl. den größeren Stapel und den leeren vertauschen

Nachdem alle Ziegel, die es links und rechts gibt, weg sind, erkennt Karol den Platz mit dem ehemals kleineren Stapel. Es ist der leere Platz! In richtiger Reihenfolgen sollte es der linke Platz sein. Falls nicht, schiebt er die Restziegel vom linken auf den rechten Platz.

Anweisung umschichten
//Karol steht vor zwei Stapeln. Einer von beiden (der vor ihm oder dessen linker) ist leer
//Karol schichtet die Ziegel des nicht leeren Stapels immer auf den rechten der beiden Stapel
//Am Ende hat immer der rechte Stapel die Ziegel
//Karol steht am Ende immer am rechten Stapel
  wenn NichtIstZiegel dann
     LinksGehen
     solange IstZiegel tue
       Aufheben RechtsGehen Hinlegen LinksGehen
     *solange
     RechtsGehen
  *wenn
*Anweisung