Das Sortierproblem

Das Sortierproblem besteht darin, Datensätze eines gegebenen Datenbestands sortiert anzuordnen. Im Folgenden geht es darum, das Sortierproblem und seine Relevanz in der Informatik genauer zu betrachten.

Beschreibung des Sortierproblems

Gegeben ist eine Liste mit Daten. Die Daten können einfach strukturiert sein (wie z.B. Zahlen), die Daten können aber auch eine komplexe Struktur haben (wie z.B. Adressangaben). Die einzige Voraussetzung, die die Daten erfüllen müssen, besteht darin, dass man sie nach einem Kriterium vergleichen kann. Es soll also möglich sein, bei zwei Daten D1 und D2 (der Ausgangsdatenliste) zu entscheiden, ob (nach dem vorgegebenen Vergleichskriterium) D1 kleiner als D2 oder D2 kleiner als D1 ist oder ob D1 und D2 bzgl. des Vergleichskriterium gleichwertig sind.

Als Beispiel betrachten wir die folgende Liste mit Adressdaten.

Krause,Stefanie,Brandenburgische Str. 20,74343,Sachsenheim
Brandt,Mandy,Scharnweberstrasse 84,68199,Mannheim Almenhof
Möller,Jens,Schoenebergerstrasse 47,08313,Bernsbach
Herzog,Marco,Scharnweberstrasse 90,61130,Nidderau
Schmitz,Andreas,Meininger Strasse 84,66539,Neunkirchen Ludwigsthal
Ebersbacher,Michelle,Alt-Moabit 10,06691,Zeitz
Koertig,Christine,Hardenbergstraße 82,66887,Niederalben
Schmidt,Vanessa,Paderborner Strasse 44,86359,Gersthofen
Meister,Stephan,Fasanenstrasse 17,22605,Hamburg Othmarschen
Schreiber,Barbara,Stresemannstr. 56,66592,St Wendel
...

Wenn die Datensätze alphabetisch nach dem Nachnamen verglichen werden sollen, dann ist der Datensatz Herzog,Marco,Scharnweberstrasse 90,61130,Nidderau kleiner als der Datensatz Schmidt,Vanessa,Paderborner Strasse 44,86359,Gersthofen. Die Datensätze Schmitz,Andreas,Meininger Strasse 84,66539,Neunkirchen Ludwigsthal und Schmitz,Laura,Joachimstaler Str. 16,54518,Arenrath wären nach dem vorgegebenen Vergleichskriterium als gleichwertig anzusehen.

Ziel einer Sortierung ist es, die Daten des gegebenen Datenbestandes der Größe nach bzgl. des gewählten Vergleichskriterium anzuordnen.

Im Beispiel würde sich folgende Anordnung ergeben:

...
Brandt,Mandy,Scharnweberstrasse 84,68199,Mannheim Almenhof
...
Ebersbacher,Michelle,Alt-Moabit 10,06691,Zeitz
...
Herzog,Marco,Scharnweberstrasse 90,61130,Nidderau
...
Koertig,Christine,Hardenbergstraße 82,66887,Niederalben
...
Krause,Stefanie,Brandenburgische Str. 20,74343,Sachsenheim
...
Meister,Stephan,Fasanenstrasse 17,22605,Hamburg Othmarschen
...
Möller,Jens,Schoenebergerstrasse 47,08313,Bernsbach
...
Schmidt,Vanessa,Paderborner Strasse 44,86359,Gersthofen
...
Schmitz,Andreas,Meininger Strasse 84,66539,Neunkirchen Ludwigsthal
...
Schreiber,Barbara,Stresemannstr. 56,66592,St Wendel
...

Das Sortierproblem besteht darin, Verfahren zu entwickeln, die eine sortierte Anordnung von Datensätzen automatisiert erzeugen.

Entwicklungen 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.

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.

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 5

Versuche, mit den vorgegebenen Operationen die gegebene Datenliste sortiert anzuordnen.
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 oder in Pseudocode algorithmisch zu beschreiben.