Bucketsort

Einfache Sprache

Bucketsort ist ein Sortierverfahren, dass ohne Elementvergleiche auskommt. Elemente werden in “Buckets” platziert und dann die Buckets nacheinander aufgereiht.

Idee Bucketsort

Gegeben ist ein Feld $A$ mit $n$ Zahlen aus $\{0,\ldots,m-1\}$. Bucketsort verwendet ein Feld von $m$ Buckets $B[0],\ldots,B[m-1]$. Jeder Bucket ist eine einfach verkettete Liste von Elementen. Zu beginn sind diese noch leer. Füge jedes Element $x$ aus $A$ in die Liste in Bucket $B[x]$ ein. Am Ende hänge alle Listen der Reihe nach aneinander. Er arbeitet out-of-place. D.h. er benötigt mehr zusätzlichen Speicherplatz.

Algorithmus

1def bucketsort(A, m):
2    n = len(A)
3    B = [[] for _ in range(m)]
4    for i in range(n):
5        B[A[i]].append(A[i])
6    for j in range(1, m):
7        B[0].extend(B[j])
8    A[:] = B[0]

Laufzeit

Bucketsort hat eine Laufzeit von $\mathcal O(m+n)$. Ist $m=\mathcal O(n)$, so ist die Laufzeit $\mathcal O(n)$.