DAA - Radix Sort

Radix sortist eine kleine Methode, die viele Leute intuitiv verwenden, wenn sie eine große Liste von Namen alphabetisieren. Insbesondere wird die Liste der Namen zuerst nach dem ersten Buchstaben jedes Namens sortiert, dh die Namen sind in 26 Klassen angeordnet.

Intuitiv könnte man Zahlen nach ihrer höchstwertigen Ziffer sortieren wollen. Die Radix-Sortierung funktioniert jedoch kontraintuitiv, indem zuerst nach den niedrigstwertigen Ziffern sortiert wird. Beim ersten Durchgang werden alle Zahlen nach der niedrigstwertigen Ziffer sortiert und in einem Array zusammengefasst. Beim zweiten Durchgang werden dann die gesamten Zahlen erneut nach den zweitniedrigsten Stellen sortiert und in einem Array kombiniert und so weiter.

Algorithm: Radix-Sort (list, n) 
shift = 1 
for loop = 1 to keysize do 
   for entry = 1 to n do 
      bucketnumber = (list[entry].key / shift) mod 10 
      append (bucket[bucketnumber], list[entry]) 
   list = combinebuckets() 
   shift = shift * 10

Analyse

Jede Taste wird einmal für jede Ziffer (oder jeden Buchstaben, wenn die Tasten alphabetisch sind) der längsten Taste gesucht. Daher, wenn der längste Schlüssel hatm Ziffern und es gibt n Schlüssel, Radix Sort hat Ordnung O(m.n).

Wenn wir uns jedoch diese beiden Werte ansehen, ist die Größe der Schlüssel im Vergleich zur Anzahl der Schlüssel relativ klein. Wenn wir beispielsweise sechsstellige Schlüssel haben, könnten wir eine Million verschiedene Datensätze haben.

Hier sehen wir, dass die Größe der Schlüssel nicht signifikant ist und dieser Algorithmus von linearer Komplexität ist O(n).

Beispiel

Das folgende Beispiel zeigt, wie die Radix-Sortierung mit sieben dreistelligen Zahlen funktioniert.

Eingang	1 st Pass	2 nd Pass	3 rd Pass
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

Im obigen Beispiel ist die erste Spalte die Eingabe. Die verbleibenden Spalten zeigen die Liste nach aufeinanderfolgenden Sortierungen an immer wichtigeren Stellen. Der Code für die Radix-Sortierung setzt voraus, dass jedes Element in einem Array enthalten istA von n Elemente hat d Ziffern, wo Ziffer 1 ist die niedrigste Ziffer und d ist die Ziffer höchster Ordnung.