Sortierverfahren

Bucket Sort und Radix Sort

 aufwärts

Bucket Sort

Bucket Sort eignet sich für den Fall, dass der Wertebereich, in dem sich die zu sortierenden Zahlen befinden, einigermaßen eng begrenzt ist.

Beispiels­weise möchte ein Verein aus Anlass der bevor­stehenden 100-Jahr-Feier die Mitglieder­kartei nach Jahren der Vereins­zugehörig­keit sortieren. Dann kommen als mögliche Werte nur Zahlen zwischen 0 und 99 vor.

Das Sortier­verfahren Bucket Sort funktioniert so: Es werden 100 Eimer (engl.: bucket) aufgestellt und mit den Zahlen von 0 bis 99 nummeriert. Die Karteikarten werden nun eine nach der anderen in die Eimer geworfen, wobei eine Karte bei k-jähriger Mitglied­schaft in den Eimer mit der Nummer k kommt. Am Ende werden die Eimer, beginnend bei Nummer 0, der Reihe nach wieder ausgeleert. Auf diese Weise ergibt sich die nach Jahren der Vereins­zugehörig­keit sortierte Mitglieder­kartei.

Analyse

Jede der n Karteikarten wird genau einmal in einen Eimer geworfen und genau einmal wieder entnommen. Die Komplexität von Bucket Sort liegt also in Θ(n).

Implementierung

Die Eimer werden als Array list von verketteten Listen dargestellt. Das Werfen einer Karteikarte in den Eimer Nummer k wird implementiert, indem ein Verweis auf die Karteikarte in die Liste list[k] eingefügt wird.

Radix Sort

Nachteilig bei dem eben geschilderten Beispiel ist der relativ hohe Aufwand von 100 Eimern. Stehen nur 10 Eimer zur Verfügung, so lassen sich die Karteikarten immerhin in zwei Durchläufen von Bucket Sort sortieren. Im ersten Durchlauf werden die Karten nach Jahrzehnten der Mitglied­schaft grob sortiert. Im zweiten Durchlauf werden die Karten, getrennt für jedes Jahrzehnt, nach Jahren sortiert.

Wären Werte bis 999 möglich gewesen, so hätten die Karten zuerst nach Jahr­hunderten, dann nach Jahrzehnten und dann nach Jahren sortiert werden müssen; es wären also drei Durchläufe von Bucket Sort erforderlich gewesen.

Dieses Verfahren heißt Radix Sort. Die Bezeichnung Radix Sort rührt daher, dass die zu sortierenden Zahlen zur Basis b (engl.: radix b) dargestellt werden, wobei b die Anzahl der zur Verfügung stehenden Eimer ist. Für jede Stelle der Zahlen­darstellung wird dann ein Durchlauf von Bucket Sort durchgeführt.

Analyse

Sind allgemein w die Anzahl der möglichen Werte und b die Anzahl der Eimer, so sind logb(w) Durchläufe erforderlich. Jeder Durchlauf benötigt Θ(n) Schritte, wenn n die Anzahl der zu sortierenden Daten ist.

Ist die Anzahl b der Eimer konstant, so ergibt sich für Radix Sort eine Komplexität von Θ(n log(w)).

Implementierung

Da die Daten im Rechner in Binär­darstellung vorliegen, bietet es sich an, mit b = 2 zu arbeiten. Implementiert wird Radix Sort meist so, dass zuerst nach dem nieder­wertigsten Bit 0 sortiert wird. Im nächsten Durchlauf wird der gesamte Datensatz nach Bit 1 sortiert, jedoch ohne dabei die Reihenfolge von Zahlen mit gleichem Bit 1 zu verändern, usw.

Folgendes Bild zeigt ein entsprechendes Vorgehen für den Fall b = 10. Zuerst wird die Folge nach der letzten Ziffer sortiert, dann nach der zweiten, dann nach der ersten.

305123013130725612122123
 
130612122123013123305725
305612013122123123725130
013122123123130305612725
 

 

Weiter:   [Median-Algorithmus]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 13.04.2002   Updated: 29.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik