Radixsort

Einfache Sprache

Das Sortierverfahren Radixsort basiert auf Bucketsort. Dabei werden die Elemente in Form von Zahlen iterativ von der niedrigsten bis zur höchsten Stelle sortiert. Der Trick dabei ist, da die Elemente nach den unteren $x-1$ Stellen sortiert sind, landen die Elemente beim Bucketsort der Stelle $x$ in der richtigen Reihenfolge im jeweiligen Bucket.

Idee Radixsort

Gegeben ist ein Feld $A$ mit $n$ natürlichen Zahlen, die aus jeweils $d$ Ziffern mit dem Wert aus $\{0,\ldots,k-1\}$ bestehen. $n$ ist also in k-adische Darstellung. Radixsort funktioniert folgendermaßen: Die $d$ Zifferpositionen seien von rechts nach links durchnummeriert. Sortiere $A$ erst nur nach der ersten Ziffer, dann nach der zweiten u.s.w. Zum Sortieren nutze immer Bucketsort.

Algorithmus

 1def radixsort(A, d, k):
 2    n = len(A)
 3    for l in range(1, d + 1):
 4        # Create k buckets
 5        buckets = [[] for _ in range(k)]
 6        # Distribute elements into buckets based on current digit
 7        # Also Sortiere A gemäß Ziffer l mit Bucketsort und k Buckets
 8        for num in A:
 9            digit = (num // (k ** (l - 1))) % k
10            buckets[digit].append(num)
11        # Collect elements from buckets in order
12        A = []
13        for bucket in buckets:
14            A.extend(bucket)
15    return A

Laufzeit

Die Laufzeit ist $\mathcal O(d(n+k))$. Ist $d=\mathcal O(1)$ und $k = \mathcal O(n)$, so ist die Laufzeit $\mathcal O(n)$.

Example

Ein Ablauf von Radixsort für $k = 10$ (Dezimaldarstellung) und $d = 3$.

| Index | $l=1$ | $l=2$ | $l=3$ | ende | | —– | ————— | ————— | ————— | ————— | | 1 | $0\quad2\quad5$ | $7\quad2\quad0$ | $0\quad0\quad4$ | $0\quad0\quad4$ | | 2 | $3\quad2\quad9$ | $0\quad0\quad4$ | $7\quad2\quad0$ | $0\quad2\quad5$ | | 3 | $0\quad0\quad4$ | $0\quad2\quad5$ | $0\quad2\quad5$ | $1\quad5\quad5$ | | 4 | $8\quad3\quad9$ | $3\quad5\quad5$ | $3\quad2\quad9$ | $3\quad2\quad9$ | | 5 | $7\quad2\quad0$ | $1\quad5\quad5$ | $8\quad3\quad9$ | $3\quad5\quad5$ | | 6 | $3\quad5\quad5$ | $3\quad2\quad9$ | $3\quad5\quad5$ | $7\quad2\quad0$ | | 7 | $1\quad5\quad5$ | $8\quad3\quad9$ | $1\quad5\quad5$ | $8\quad3\quad9$ |