Karl soll Ziegelstapel der Größe nach sortieren.

Karl soll mehrere Ziegelstapel der Größe nach sortieren. Hierzu zerlegt er das Problem in viele kleinere Probleme. So sortiert er zunächst nur zwei Stapel, anschließend drei und zum Schluß eine beliebige, vorher unbekannte Menge von Ziegelsteinen, zwischen denen sich jeweils ein Leerplatz befindet.Video (Youtube)

1. Schritt: Sortieren von zwei Ziegelstapeln

Karl steht zwischen zwei Ziegelstapeln beliebiger Höhe. Er soll herausfinden, ob der vordere oder der hintere Stapel mehr Ziegelsteine hat. Ist der vordere Stapel höher, soll er die Stapel vertauschen.

Wie könnte Karl vorgehen? Beachte: Er hat nur die Befehle Aufheben LinksDrehen Schritt RechtsDrehen und Hinlegen zur Verfügung.
Gliedere deinen Algorithmus, indem du eigene Anweisungen und eigene selbstdefinierte Bedingungen definierst.

Idee für einen Algorithmus

Lege solange „vorne und hinten ein Ziegel ist“, jeweils eine Ziegellage zur Seite.

Fehlt hinten oder vorne ein Ziegel legt man im Fall, dass vorne noch Ziegel liegen alle Ziegel nach hinten. Ist vorne keine Ziegel mehr, so war hinten der gößere Stapel. 

Anschließend legt man die zuvor weggelegten Steine wieder auf den alten Platz.

möglicher Quelltext
Anweisung Umdrehen
  LinksDrehen
  LinksDrehen
*Anweisung

Bedingung VorneUndHintenZiegel
  wenn NichtIstZiegel dann falsch
    sonst
    Umdrehen
    wenn NichtIstZiegel dann falsch sonst wahr *wenn
    Umdrehen
  *wenn
*Bedingung

Anweisung EineLageZiegelZurSeite
  Aufheben
  LinksDrehen
  Schritt
  RechtsDrehen
  Hinlegen
  RechtsDrehen
  Schritt
  RechtsDrehen
  Aufheben
  RechtsDrehen
  Schritt
  LinksDrehen
  Hinlegen
  LinksDrehen
  Schritt
  LinksDrehen
*Anweisung

Anweisung ZiegelNachHinten
  wiederhole solange IstZiegel
    Aufheben
    Umdrehen
    Hinlegen
    Umdrehen
  *wiederhole
*Anweisung

{ab hier gehts los}

wiederhole solange  VorneUndHintenZiegel
  EineLageZiegelZurSeite
*wiederhole

wenn IstZiegel dann ZiegelNachHinten *wenn

LinksDrehen
Schritt
LinksDrehen

wiederhole solange   VorneUndHintenZiegel
  EineLageZiegelZurSeite
*wiederhole

LinksDrehen
Schritt
LinksDrehen

2. Schritt: Karl soll drei Stapel sortieren

Karl soll jetzt 3 Stapel sortieren. Dazu vergleicht er zunächst die ersten zwei Stapel, dann geht er in den nächsten Zwischenraum und vergleicht diese. 

Welche Höhe haben die einzelnen Stapel nach einem Durchgang? 

Wie viel Durchgänge muss Karl maximal machen, damit alle Stapel sortiert sind?

Definiere folgende Unteranweisungen:

  1. Gehe in den nächsten Zwischenraum.
  2. Gehe wieder zurück an den Ausgangspunkt.

 

3. Schritt: Karl sortiert mehrere Stapel

Karl sortiert mehrere Stapel.

Zunächst legt er für jedes zu vergleichende Stapelpaar sich einen Stein zur Seite. Als Hilfe kann man bei der Generierung der Welt zwischen das letzte Stapelpaar eine Marke setzen. Dies kann Karl allerdings auch am Anfang selbst erledigen.

Bei jedem Durchgang nimmt er einen Stein fort, so weiß Karl wann er den letzten Durchgang zu machen hat.

4. Schritt: Karl sortiert mehrere Stapel

Karl sortiert beliebige Stapel. Allerdings nicht mehr, als die Höhe seiner Welt es zulässt. 

 

Hier könnte man den Algorithmus noch verändern, wenn man diese Einschränkung nicht zulassen möchte.

Welche Erweiterungen wären sonst noch möglich?

Programmbibliothek
// Sortieralgorithmus
Anweisung Umdrehen
  Schnell
  RechtsDrehen
  RechtsDrehen
  Langsam
*Anweisung



Bedingung NichtRechtsMarkeZiegel
  Schnell
  wahr
  RechtsDrehen
  wenn NichtIstZiegel dann Schritt
    wenn IstMarke dann falsch *wenn
    Umdrehen
    Schritt
    Umdrehen
  *wenn
  LinksDrehen
  Langsam
*Bedingung

Anweisung MarkenAufräumen
  LinksDrehen
  Schritt
  RechtsDrehen
  wiederhole solange NichtRechtsMarkeZiegel
    Schritt
  *wiederhole
  RechtsDrehen
  Schritt
  MarkeLöschen
  RechtsDrehen
  RechtsDrehen
  Schritt
  LinksDrehen
  wiederhole solange NichtIstMarke
    Schritt
  *wiederhole
  MarkeLöschen
  LinksDrehen
  Schritt
  LinksDrehen
*Anweisung


Bedingung NichtRechtsMarkeZiegel
  wahr
  RechtsDrehen
  wenn NichtIstZiegel dann Schritt
    wenn IstMarke dann falsch *wenn
    Umdrehen
    Schritt

  *wenn
  RechtsDrehen
*Bedingung

Bedingung NochEinDurchgang
  Schnell
  falsch
  LinksDrehen
  Schritt(2)
  wenn IstZiegel dann wahr
    Aufheben
  *wenn
  Umdrehen
  Schritt(2)
  LinksDrehen
  Langsam
*Bedingung


Bedingung  ZiegelVorneUndHinten  // Bedingung wahr falls Vo u. Hi. Ziegel
  Schnell
  falsch
  wenn IstZiegel dann
    Umdrehen
    wenn IstZiegel dann wahr *wenn
    Umdrehen
  *wenn
  Langsam
*Bedingung

Bedingung IstRechtsZiegel
  Schnell
  falsch
  RechtsDrehen
  wenn IstZiegel dann wahr *wenn
  LinksDrehen
  Langsam
*Bedingung


Anweisung GeheVor
  Schnell
  LinksDrehen
  Schritt
  RechtsDrehen
  Schritt(2)
  RechtsDrehen
  Schritt
  LinksDrehen
  Langsam
*Anweisung


Anweisung ZiegelAufAndereSeite  //schaufelt Ziegel von Vorne nach Hinten oder umgekehrt
  Schnell
  wiederhole solange IstZiegel
    Aufheben
    Umdrehen
    Hinlegen
    Umdrehen
  *wiederhole
  Langsam
*Anweisung

Anweisung ZiegelZurSeiteSchaffen    // Legt jeweils eine Lage zur Seite
  wiederhole solange  ZiegelVorneUndHinten
    Aufheben
    LinksDrehen
    Schritt
    LinksDrehen
    Hinlegen
    LinksDrehen
    Schritt
    RechtsDrehen
    Aufheben
    RechtsDrehen
    Schritt
    RechtsDrehen
    Hinlegen
    RechtsDrehen
    Schritt
    LinksDrehen
  *wiederhole

*Anweisung



Anweisung GrosserStapelNachHinten  // Hauptanweisung

  ZiegelZurSeiteSchaffen
  ZiegelAufAndereSeite
  LinksDrehen
  Schritt
  LinksDrehen
  ZiegelZurSeiteSchaffen
  LinksDrehen
  Schritt
  LinksDrehen

*Anweisung

Anweisung Zurueck  // läuft von der unteren Marke zur oberen Marke
  // und dann zurück zum Ausgangspunkt
  Schnell
  LinksDrehen
  Schritt
  LinksDrehen
  wiederhole solange NichtIstMarke
    Schritt
  *wiederhole
  LinksDrehen
  Schritt
  LinksDrehen
  Langsam
*Anweisung

Anweisung MarkeAmAnfangSetzen
  Schnell
  LinksDrehen
  Schritt
  MarkeSetzen
  Umdrehen
  Schritt
  LinksDrehen
  Langsam
*Anweisung


Anweisung ProStapelEinenZiegelHinlegen
  Schnell
  LinksDrehen
  Schritt
  RechtsDrehen
  Schritt

  wiederhole solange IstRechtsZiegel
    LinksDrehen
    Hinlegen
    RechtsDrehen
    Schritt(2)
  *wiederhole
  Umdrehen
  Schritt(3)
  LinksDrehen
  Schritt
  MarkeSetzen
  Umdrehen
  Schritt
  RechtsDrehen
  Schritt(2)
  LinksDrehen
  Schritt
  MarkeSetzen
  Umdrehen
  Schritt
  RechtsDrehen
  wiederhole solange NichtIstMarke
    Schritt
  *wiederhole
  LinksDrehen
  Schritt
  LinksDrehen
  Langsam
*Anweisung

Anweisung ZiegelZaehlen    // Legt einen! seitlichen Ziegel auf einen Stapel
  // dieser dient zum Zählen der Durchgänge
  Schnell
  Aufheben
  Schritt
  RechtsDrehen
  Schritt
  RechtsDrehen
  wiederhole solange NichtIstMarke
    Schritt
  *wiederhole
  RechtsDrehen
  Schritt
  Hinlegen
  RechtsDrehen
  Langsam
*Anweisung

Anweisung ZiegelEinsammeln
  Schnell
  LinksDrehen
  Schritt(2)
  RechtsDrehen
  wiederhole solange NichtIstMarke
    wenn IstZiegel dann ZiegelZaehlen *wenn
    Schritt
  *wiederhole
  MarkeLöschen
  RechtsDrehen
  Schritt
  RechtsDrehen
  wiederhole solange NichtIstMarke
    Schritt
  *wiederhole
  LinksDrehen
  Schritt
  LinksDrehen
  // zum Schluß noch einen Ziegel wegnehmen
  LinksDrehen
  Schritt(2)
  Aufheben
  Umdrehen
  Schritt(2)
  LinksDrehen
  Langsam
*Anweisung

Anweisung MarkenAufraeumen
  LinksDrehen
  Schritt
  RechtsDrehen
  wiederhole solange NichtRechtsMarkeZiegel
    Schritt
  *wiederhole
  RechtsDrehen
  Schritt
  MarkeLöschen
  Umdrehen
  Schritt
  LinksDrehen
  wiederhole solange NichtIstMarke
    Schritt
  *wiederhole
  MarkeLöschen
  LinksDrehen
  Schritt
  LinksDrehen
*Anweisung
Programm - Quelltext
{Karl sortiert eine beliebige Anzahl}  
{weniger als 6}
Einfügen
sortieren_bibliothek.kdp
*Einfügen

MarkeAmAnfangSetzen
ProStapelEinenZiegelHinlegen
ZiegelEinsammeln

wiederhole solange NochEinDurchgang
  wiederhole solange NichtIstMarke
    GeheVor
    GrosserStapelNachHinten
  *wiederhole
  Zurueck
*wiederhole

MarkenAufräumen

Sortieralgorithmen als Volkstanz

Bubble Sort

Select Sort

Insert Sort

Zurück