Kurs:Algorithmen und Datenstrukturen/Kapitel 2/BucketSort

Bei Bucketsort werden nach vorgegebenen Kriterien Datensätze in „Eimer“ verteilt. Man kann sich das so vorstellen, dass die Eimer jeweils eine Nummer haben, dann schaut man auf den Schlüssel des Datensatzes und entscheidet, in welchen Eimer der Datensatz kommt. Damit man dies sinnvoll machen kann, muss es eine Ordnungsrelation der Schlüssel geben und man benötigt eine Funktion, mit deren Hilfe man vom Wert des Schlüssels aus die Nummer des Eimers bestimmen kann.

Hat man für Schlüsselwerte die Relation

a < b < c

dann muss für die Funktionswerte

f(a) < f(b) < f(c)

gelten, wobei die Funktion immer einen ganzzahligen Wert liefern muss, denn einen Eimer 3 ½ gibt es nicht.

Die einfachste Art, wie man solch eine Funktion definieren kann, besteht in der Definition von Grenzwerten. Gilt etwa für den Eimer mit der Nummer 0 , dass der Wert des Schlüssels größer gleich Null sein soll und kleiner 10, für den Eimer mit der Nummer 1, dass der Wert des Schlüssels größer gleich 10 und kleiner als 30 sein soll, ......, so hat man eine einfache Zuordnung von Schlüsselwert auf Eimernummer. Es ist aber auch jegliche andere Realisierung möglich.

Im Allgemeinen sammeln sich in den Eimern Datensätze, deren Schlüsselwerte nahe beieinander liegen, aber dennoch verschieden sind. Man muss also ein weiteres Sortierverfahren einsetzen, um wiederum die Inhalte der Eimer zu sortieren, wozu man natürlich auch wieder Bucketsort einsetzen kann, dann allerdings mit anderen/abgewandelten Verteilerfunktionen.

Es ist ersichtlich, dass Bucketsort für generelle Sortieraufgaben nicht besonders gut geeignet ist, da jeweils ein spezialisierter Satz an Verteilerfunktionen bereit gestellt werden muss.

Es lassen sich die Verteilerfunktionen mit relativ wenig Aufwand automatisch ableiten. Hierbei wird die jeweils zu verwendende Anzahl der Eimer vorgegeben. Dann bestimmt man den größten und den kleinsten Wert der Schlüssel und teilt den Bereich linear entsprechend der Anzahl der Eimer auf. Bei gleichmäßig verteilten Werten funktioniert dies recht gut; bei stark ungleichmäßig verteilten Schlüsselwerten muss man gegebenenfalls den Weg über Histogramme gehen.

Hat man n Datensätze, so benötigt man n mal die Verteilerfunktion, um die Datensätze auf den ersten Satz Eimer zu verteilen. Ist nur ein Durchlauf notwendig, etwa bei der Erstellung eines Histogrammes, so wächst die Zeit für die Sortierung linear mit der Anzahl der Datensätze. Muss man Bucketsort rekursiv anwenden, dann werden die Inhalte der Eimer auf "Untereimer" verteilt; hierbei werden aber auf jeder Teilungsebene wieder alle n Schlüssel mit (verschiedenen) Verteilerfunktionen bewertet und verteilt. Wieviele Wiederholungen benötigt werden, ergibt sich aus der Anzahl der Eimer, die als Teilungsfaktor dient. Teilt man die Intervalle immer in zehn Bereiche, so ergibt sich der Zeitbedarf für Bucketsort durch

T = C * n * lg₁₀(n)

wobei C eine implementationsabhängige Konstante ist.