I had to implement radix sort for my class today for my last assignment.
It looked pretty cool so I thought I'd share
[highlight=python]
from Queue import Queue
from math import log
def radix_sort(items):
buckets = [] # our buckets
highest = max(abs(x) for x in items)
if highest != 0:
longest = int(log(highest)+1) # the length of the longest number
else:
longest = 1
for i in range(19):
buckets.append(Queue()) # fill 19 buckets with Queues
for k in range(longest):
for i in items:
d = (abs(i) // (10**k) ) % 10 # kth digit in number
if i >= 0:
buckets[9+d].put(i) # add to the positives
else:
buckets[9-d].put(i) # add to the negatives
t = 0
for bucket in buckets:
for j in range(bucket.qsize()):
items[t] = bucket.get() # reconstruct list
t += 1
[/highlight]
Note that items has to be a list of integers in base 10 (Anything belonging to Z).
It looked pretty cool so I thought I'd share
[highlight=python]
from Queue import Queue
from math import log
def radix_sort(items):
buckets = [] # our buckets
highest = max(abs(x) for x in items)
if highest != 0:
longest = int(log(highest)+1) # the length of the longest number
else:
longest = 1
for i in range(19):
buckets.append(Queue()) # fill 19 buckets with Queues
for k in range(longest):
for i in items:
d = (abs(i) // (10**k) ) % 10 # kth digit in number
if i >= 0:
buckets[9+d].put(i) # add to the positives
else:
buckets[9-d].put(i) # add to the negatives
t = 0
for bucket in buckets:
for j in range(bucket.qsize()):
items[t] = bucket.get() # reconstruct list
t += 1
[/highlight]
Note that items has to be a list of integers in base 10 (Anything belonging to Z).