Radix sort algorithm in Python question
Ray Van Dolson
rayvd at nospam.firetail.org
Wed Feb 7 01:32:44 EST 2001
I'm designing a Radix sort algorithm in Python (for an assignment). I have
the algorithm done, but it's not exactly fast. Since I'm supposed to be
comparing this to Quicksort (my Python Quicksort implementation is -
infinitely- faster). Here's the code:
def rSort(a,n,maxLen):
bins=[[],[],[],[],[],[],[],[],[],[],[]]
for x in range(0,maxLen):
if x == 0:
for y in a:
bins[y%n].append(y)
else:
for y in a:
origValue=y
if y < 10**x:
bins[0].append(y)
else:
y=y/(10**x)
bins[y%n].append(origValue)
del a
a=[]
for section in bins:
if len(section) > 0:
for times in range(0,len(section)):
a.append(section.pop(0))
I'm guessing the problem lies when I am taking the elements out of the
"bins" and putting them back into the array. I delete the array and then
step through the bins popping the numbers out. When we're talking about
thousands of elements this takes a while.
Anyone have any suggestions on how I could better streamline this? I don't
think radix should be 40 times slower than quicksort, but I could be wrong.
Thanks,
Ray Van Dolson
More information about the Python-list
mailing list