Lineare Datenstrukturen

nochmals Sortieren

Stell dir vor, du sortierst mit Bucket-Sort 20 Datensätze mit Schlüsseln zwischen 0 und 999 999.

Was trifft zu?

Man braucht 20 Eimer
Man braucht 1 Million Eimer
Genau 20 Eimer werden gefüllt
Höchstens 20 Eimer werden gefüllt
Auch leere Eimer brauchen Platz und Zeit
(bei einer Realisierung im Computer)

Radix (engl.) = Basis

Das Verfahren Radix-Sort ist eine raffinierte Variante von Bucket-Sort.

Voraussetzung

Die Schlüssel sind natürliche Zahlen. Bei Darstellung zur Basis b (z. B. b = 2: Dualsystem, b=10: Dezimalsystem) benötigt man maximal k Ziffern.

Algorithmus

Stelle b Eimer bereit. Jeder Eimer ist eine Queue.
Führe bezüglich der letzten Ziffer (Einerstelle) einen Bucket-Sort durch.
Führe bezüglich der zweitletzten Ziffer einen Bucket-Sort durch.
usw. bis zur vordersten Ziffer.

Ändere auch die Basis!

Dank

Alles klar? Hier sind ein paar Kontrollfragen.

wieder nachdenken ...

Welche Aussagen sind richtig?

Beim Radix-Sort wird Bucket-Sort ...

... k-mal durchgeführt.
... b-mal durchgeführt.

Nach dem zweiten Durchgang sind die Datensätze bzgl. der...

... letzten Ziffer sortiert.
... beiden letzten Ziffern sortiert.
... zweitletzten Ziffer sortiert.

Radix-Sort funktioniert ...

... weil Bucket-Sort stabil ist
... nur mit Bucket-Sort
... auch, wenn man Bucket-Sort durch irgendein anderes
Sortierverfahren ersetzt
... auch, wenn man Bucket-Sort durch irgendein anderes,
stabiles Sortierverfahren ersetzt

Würde man die Bucket-Sorts in umgekehrter Reihenfolge durchführen (zuerst die höchste Stelle, zum Schluss die Einerstelle), dann wären die Zahlen anschließend...

... von klein nach groß sortiert.
... von groß nach klein sortiert.
... im Allgemeinen gar nicht sortiert.

Das Sortierverfahren Radix-Sort ist...

... stabil.
... nicht stabil.

Wie oft werden bei der Sortierung mit Radix-Sort Datensätze in Eimer bewegt, wenn man 20 Datensätze mit Schlüsseln zwischen 0 und 999 999 zur Basis 10 sortiert?

Und bei Basis b=2?

Und bei Basis b=1 000?