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