Lineare Datenstrukturen

Anwendung

Das Sortieren von Datensätzen ist eine der wichtigsten Aufgaben der Datenverarbeitung.

Begriffe

Das Kriterium, wonach man sortiert, heißt Schlüssel.
Mögliche Schlüssel sind u. A.

Wörter (alphabetische Sortierung)
Datumsangaben (zeitliche Sortierung)
Zahlen (Sortierung nach Größe)

Wir sortieren hier Datensätze mit Zahlen als Schlüssel.

Bucket (engl.) = Eimer

Bucket-Sort ist ein einfaches Sortierverfahren.

Voraussetzung

Es ist bekannt, dass die Schlüssel nur b verschiedene Werte annehmen, z. B. nur die Werte 0 bis 9 (b = 10).

Algorithmus

Stelle b "Eimer" auf, einen für jeden möglichen Schlüsselwert.
Verschiebe der Reihe nach die Datensätze in die Eimer:
Ein Datensatz mit Schlüssel s kommt in Eimer s.
Entleere die Eimer der Reihe nach in eine Queue.

Dank

Warum verwendet man Queues beim Bucket-Sort?

hier muss man etwas nachdenken!

Warum werden die Eimer am Ende in eine Queue entleert?

Damit die Folge am Ende sortiert ist
Weil es wichtig ist, dass man immer nur
am Ende einfügen kann
Es gibt keinen besonderen Grund

Warum ist jeder einzelne Eimer als Queue realisiert?

Damit die Folge am Ende sortiert ist
Damit beim Füllen der Eimer die Datensätze mit gleichem
Schlüssel ihre Reihenfolge beibehalten.
Damit Datensätze mit gleichem Schlüssel nach Entleerung
der Eimer ihre Reihenfolge beibehalten
Es gibt keinen besonderen Grund

Stabilität

Bei Bucket-Sort ändern Datensätze mit gleichem Schlüssel ihre Reihenfolge untereinander nicht.
Sortierverfahren mit dieser Eigenschaft nennt man stabil.

Beispiel

Die Datensätze einer Personaldatei sind bzgl. der Nachnamen alphabetisch sortiert. Ein Sortierverfahren ordnet die Datensätze nach dem Geburtsjahr. Ist das Sortierverfahren stabil, so bleiben die Datensätze eines Jahrgangs in sich alphabetisch nach Nachnamen sortiert.