Entwicklung von Sortieralgorithmen

Einen Datenbestand sortieren

Deine Aufgabe ist es im Folgenden, ein Sortierverfahren zu entwickeln.

Für die Entwicklung von Sortierverfahren spielt die Komplexität der Daten keine zentrale Rolle. Wir gehen daher im Folgenden von einfachen Datenobjekten (hier Zahlen) aus.

Wenn ein Mensch diese Zahlen der Größe nach ordnet, dann geht er/sie in der Regel intelligent vor. Auf einen Blick erkennt er/sie bereits Auffälligkeiten und berücksichtigt diese bei der Vorgehensweise.

Ein Computer hat in der Regel keinen Überblick über alle Daten. Er kann zudem (in der Regel) nicht so intelligent wie ein Mensch agieren. Wir werden das jetzt berücksichtigen, indem wir versuchen, mit eingeschränkten Möglichkeiten wie ein Computer vorzugehen.

Version 1 - Gewichte sortieren

Vor dir liegen Gegenstände, die du mit Hilfe der Vergleichswaage sortieren sollst. Du kannst die Gegenstände auf die Waage legen und verleichen und anschließend auch wieder neben/unter der Waage platzieren.

Statt mit einer realen Waage und realen Gegenständen zu arbeiten kannst du auch das Simulationsprogramm Waage.jar oder waage.exe benutzen.

Aufgabe 1

(a) Sortiere die vorgegebenen Gewichte der Größe nach. Beschreibe die Strategie, die du verwendet hast. Funktioniert die Strategie für beliebige Gewichte? Probiere das aus. Wenn ja, dann beschreibe das Sortierverfahren möglichst präzise.

(b) Entwickle hieraus einen Algorithmus zum Sortieren von Datenobjekten (wie z.B. Zahlen).

Version 2 - Karten sortieren

Wir gehen davon aus, dass eine Folge von Zahlen auf Karteikarten notiert ist - jede Zahl auf einer eigenen Karte. Um die Arbeitsweise eines Computers zu simulieren, legen wir Regeln fest, die beim Sortieren beachtet werden müssen. Zunächst einmal werden alle Karten umgedreht. Der "Sortierer" hat keine Gesamtsicht auf alle Daten.

Folgende Operationen darf der "Sortierer" jetzt ausführen:

Regel 1: Maximal 2 Karten umdrehen:

Regel 2: 2 Karten vergleichen und in Abhängigkeit des Ergebnisses weiteragieren:

Regel 3: Eine Karte markieren (es dürfen auch mehrere unterscheidbare Marken benutzt weren):

Regel 4: Eine Karte an eine andere Stelle verschieben:

Regel 5: Karten austauschen (d.h. zwei Karten geeignet verschieben):

Weitere sinnvolle Regeln kannst du nach Bedarf einführen.

Aufgabe 1

(a) Versuche, mit den vorgegebenen Operationen die gegebene Datenliste sortiert anzuordnen.

(b) Formuliere das Verfahren, das du zum Sortieren benutzt hast. In einem ersten Schritt kannst du das umgangssprachlich tun. Versuche anschließend, das Verfahren mit einem Struktogramm algorithmisch zu beschreiben.