Beschreibung des Sortierproblems

Einen Datenbestand sortiert anordnen

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.