Entwicklung von Sortierverfahren

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 Daten (hier Zahlen) aus.

Zahlenliste

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 eingschrä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.

Zahlenliste

Statt mit einer realen Waage und realen Gegenständen zu arbeiten kannst du auch das Simulationsprogramm WaageJFrame.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 Daten(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.

Zahlenliste

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

Regel 1: Maximal 2 Karten umdrehen:

Zahlenliste

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

Zahlenliste

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

Zahlenliste

Regel 4: Eine Karte an eine andere Stelle verschieben:

Zahlenliste

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

Zahlenliste

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.

X

Fehler melden

X

Suche