Annahme:
Es existieren nur verschiedene Schlüssel.
Algorithmus:
Beim Bucket Sort werden die zu sortierenden Elemente in Buckets geworfen.
Dann werden die Buckets mit einem vergleichsbasierten Algorithmus sortiert.
Komplexität für Elemente: Average Case
Annahme:
Die zu sortierenden Elemente sind -stellige Zahlen bzgl. Basis .
Dies lässt sich natürlich auch auf -stellige Strings mit lexikographisch geordneten
Zeichen abbilden (ASCII: ).
Algorithmus:
Der Radix Sort ist eine Verallgemeinerung des Bucket Sort und benutzt
Buckets und bis zu Durchläufe zur Sortierung aller Elemente.
Algorithmus:
Der Backward Radix Sort liest die Zahlen von hinten nach vorn.
Im -ten Lauf werden die Elemente aufsteigend aus den Buckets genommen und
gemäß der -ten Stelle in neue Buckets geworfen.
Komplexität für Elemente:
Algorithmus:
Der Standard Forward Radix Sort liest die Zahlen von vorn nach hinten.
Die Buckets werden separat rekursiv sortiert (durch Aufspaltung jedes Buckets in
weitere Buckets).
Algorithmus:
Der Forward Radix Sort with Groups weist jeder Zahl eine Gruppennummer zu,
so dass am Ende die Gruppennummern der sortierten Reihenfolge der Zahlen entprechen.
Beim ersten Durchlauf des Forward Radix Sort erhalten alle Zahlen im ersten Bucket die Nummer 1,
alle Zahlen im zweiten Bucket Nummer , alle im dritten Bucket
usw.
Beim nächsten Lauf werden die Gruppen entsprechend der zweiten Stelle weiter unterteilt,
bis alle Gruppen Kardinalität 1 aufweisen oder alle Stellen der Zahl durchprobiert wurden.
Sortierverfahren | Komplexität | stabil | Speicherbedarf |
Bubblesort | ja | -- | |
Einfügesort | ja | -- | |
Auswahlsort | ja | -- | |
HeapSort | nein | -- | |
MergeSort | ja | bei Arrays | |
QuickSort | , Worst Case | nein | -- |
BucketSort | , i.A. | ja | |
RadixSort | nein |