Radix Sort (Updated)

[Nimsical]

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

 

[Moca]

What happens when the largest number in the list is 0?

 

[explosions]

What happens when the largest number in the list is 0?

You use F#?

 

[Moca]

You use F#?

Yes.

 

[Nimsical]

Thank you, Moca.
Just fixed that. And if the largest number is negative. (which is against the domain of log)

 

[explosions]

Yes.

I wasn't asking if you used it, I was asking whether that would solve the problem, in your opinion.

 

[Moca]

Thank you, Moca.
Just fixed that. And if the largest number is negative. (which is against the domain of log)

Now that your program accepts negatives, does it sort them properly?

I wasn't asking if you used it, I was asking whether that would solve the problem, in your opinion.

I know what you were asking

I couldn't help myself. I've never written a radix sort before I felt that that needed to change.

let radixSort (list:int array) : int array =
    let largestInt = Array.maxBy abs list
    let largestIntLen = if largestInt = 0 then 1 else (int(log10(abs(largestInt |> double))) + 1)
    for i = 0 to largestIntLen - 1 do
        let mutable buckets = Array.create 19 (List.empty<int>)
        for number in list do
            let nthDigit nth number = int(abs(number) / int(10. ** (float (nth)))) % 10
            let nth = nthDigit i number
            if(number < 0)    then buckets.[9 - nth] <- (List.append buckets.[9 - nth] [number]) // Sort negatives properly
            elif(number >= 0) then buckets.[9 + nth] <- (List.append buckets.[9 + nth] [number]) // Sort 0 and positives properly
        let mutable listIndex = 0
        for bucket in buckets do
            for num in bucket do
                list.[listIndex] <- num
                listIndex <- listIndex + 1
    list

 

[Nimsical]

Now that your program accepts negatives, does it sort them properly?

Yes it does, as your algorithm (which is practically a copy of mine in another language) does so too. Although I'm thinking of a way to do it with 10 buckets instead of 20.

 

[Moca]

Yes it does, as your algorithm (which is practically a copy of mine in another language) does so too. Although I'm thinking of a way to do it with 10 buckets instead of 20.

I used 19. Huge difference. I win.

 

[Nimsical]

Yeah I'm not sure why I'm using 20, 19 would work exactly the same with my algorithm. (i.e one list is empty at all times since there is no -0)

(EDIT: and now mine uses 19 buckets aswell )

 

[Moca]

highest = abs(max(items))
if highest != 0:
    longest = int(log(highest)+1) # the length of the longest number

How about if it's fed a list like this?
[-3; 8;4;-4; -1202324324; -10; 0; 2; 6;-2343;-79436; 1]

abs(max(items)) will return 8
int(log(8) + 1) will return 1

k will go up to 1, and the loop will run once. 1 iteration isn't enough to sort the above list.

 

[Nimsical]

highest = abs(max(items))
if highest != 0:
    longest = int(log(highest)+1) # the length of the longest number

How about if it's fed a list like this?
[-3; 8;4;-4; -1202324324; -10; 0; 2; 6;-2343;-79436; 1]

abs(max(items)) will return 8
int(log(8) + 1) will return 1

k will go up to 1, and the loop will run once. 1 iteration isn't enough to sort the above list.

Good point.
The fix is:
[highlight=python]
max(abs(x) for x in items)
[/highlight]

Gotta love python

 

[Moca]

Good point.
The fix is:
[highlight=python]
max(abs(x) for x in items)
[/highlight]

Gotta love python

Yeah, well F#:

Array.maxBy abs list

Pass the function abs to the function maxBy and apply it to each item in list to find the max.

Gotta love F#

 

[Nimsical]

Yeah, well F#:

Array.maxBy abs list

Pass the function abs to the function maxBy and apply it to each item in list to find the max.

Gotta love F#

Hehe, yeah it doesn't look that bad