Das Sortierproblem

Einen Datenbestand durchsuchen

Umfangreiche Datenbestände gibt es in Hülle und Fülle. Oft steht man vor dem Problem, nach einem bestimmten Datensatz in einem gegebenen Datenbestand zu suchen. Dabei macht es einen großen Unterschied, ob der Datenbestand sortiert oder unsortiert ist.

Wir spielen das im Folgenden hier einmal durch. Gegeben ist eine Datei mit Adressen von Personen.

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

Beachte, dass die Adressen hier Pseudo-Adressen sind. Die Personen gibt es in der Wirklichkeit nicht. Auch die Straßenangaben gibt es (in der Regel) in den betreffenden Orten nicht.

Aufgabe 1

(a) Lade die Adressdatei adressdaten.csv herunter und öffne sie mit einem Texteditor.

Suche jetzt den Datensatz zur Person "Katja Herrmann aus Queidersbach". Eine vom Texteditor zur Verfügung gestellte Suchfunktion darfst du natürlich nicht benutzen.

(b) Lade auch die sortierte Datei adressdaten_sortiert_name.csv herunter und öffne sie mit einem Texteditor.

Suche jetzt nochmal den Datensatz zur Person "Katja Herrmann aus Queidersbach". Warum fällt einem die Suche jetzt viel leichter?

(c) Begründe, warum man gerade bei großen Datenbeständen Operationen benötigt, die die Datensätze nach bestimmten Kriterien sortiert anordnen.

Einen Datenbestand sortiert anordnen

Ziel einer Sortierung ist es, die Daten eines gegebenen Datenbestandes der Größe nach anzuordnen. Hierzu benötigt man ein Vergleichskriterium, mit dem man bei je zwei Datenobjekten aus dem Datenbestand entscheiden kann, welches Datenobjekt kleiner ist oder ob beide nach diesem Kriterium gleich 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
...

Die Datensätze sollen alphabetisch nach dem Nachnamen sortiert werden. Das Vergleichskriterium ist also "der Nachname von ... liegt alphabetisch vor ..." bzw. anderfalls "die Nachnamen von ... und ... sind gleich". Beispielsweise 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.

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

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

Dabei spielt es keine entscheidende Rolle, wie kompliziert die Datenobjekte des Datenbestandes sind. Wir können uns bei der Entwicklung von Sortierverfahren erst einmal auf ganz einfache Datenbestände fokussieren. Ein ganz einfacher Datenbestand sind Zahlen. Im Folgenden betrachten wir die Situation, dass eine Liste von Zahlen gegeben ist. Ziel ist es, diese Zahlen aufsteigend der Größe nach anzuordnen.