Radix sort algorithm in Python question

[Greg Jorgensen]

In article <g_5g6.12851$1%2.627095 at sjc-read.news.verio.net>,
  rayvd at nospam.firetail.org (Ray Van Dolson) wrote:
> 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:

You can improve the function by moving some stuff out of the loops, and
eliminating some special cases. For example, you calculate 10**x twice
each time through your inner loop. Compute it once in the outer loop.
The special case for x==0, tested each time through the outer loop even
though it will only happen once, and the unnecessary test for y < 10**x
each time through the inner loop can be eliminated.

You don't need the parameter n, since the sort radix must be 10 for
this algorithm (which relies on the modulus operator). And the function
can figure out maxLen (number of passes required to sort all of the
values) itself. Finally, the nested loops to copy the values from the
bins back to the list can be turned into a single loop.

Here's my version:

---
def rsort(a):
    "sort list of integers using base-10 radix sort"

    if a:
        bins = [ [],[],[],[],[],[],[],[],[],[] ]

        # get largest element to determine when sort is done
        m = max(a)
        # decimal digit currently partitioning on (1,10,100...)
        r = 1

        while m > r:
            # append each element of a to the end of the bin
            # corresponding to the partition digit
            for e in a:
                bins[(e/r)%10].append(e)

            r = r * 10

            # move values from bins back to a single list
            a = []
            for i in range(10):
                a.extend(bins[i])
                bins[i] = []

    return a
---

I'm sure my implementation can be refined and sped up, but already it
is about 3 times faster than your original. I created a 10,000 element
list of random integers ranging from 1 to 99999. On my system (Python
2.0) my function sorts the list in 0.54 seconds, and yours runs in 1.5
seconds.


>
> 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))
>


--
Greg Jorgensen
Portland, Oregon, USA
gregj at pobox.com


Sent via Deja.com
http://www.deja.com/