Skip to content

Instantly share code, notes, and snippets.

@sahid
Created February 24, 2013 00:42
Show Gist options
  • Save sahid/5022081 to your computer and use it in GitHub Desktop.
Save sahid/5022081 to your computer and use it in GitHub Desktop.
Bucket Sort in Python
def bsort(A):
"""Returns A sorted. with A = {x : x such that 0 <= x < 1}."""
buckets = [[] for x in range(10)]
for i, x in enumerate(A):
buckets[int(x*len(buckets))].append(x)
out = []
for buck in buckets:
out += isort(buck)
return out
def isort(A):
if len(A) <= 1: return A
i = 1
while i < len(A):
k = A[i]
j = i - 1
while j >= 0 and A[j] > k:
A[j+1] = A[j]
A[j] = k
j -= 1
i += 1
return A
@MonicaRen
Copy link

did not understand why
"buckets[int(x*len(buckets))].append(x)"

sould be i | len(buckets)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment