Quantcast

Maximum PC

It is currently Tue Sep 02, 2014 12:20 pm

All times are UTC - 8 hours




Post new topic Reply to topic  [ 10 posts ] 
Author Message
 Post subject: Problem implementing a Radix sort
PostPosted: Mon Feb 02, 2009 7:43 pm 
Little Foot
Little Foot
User avatar

Joined: Mon Jul 28, 2008 1:39 pm
Posts: 123
I am implementing a Radix sort, (not for school) and it just doesn't seem to work.
Code:
public static void radixSort(int[] a) {
        for(int x=1; x<=2; x++) {
            Bucket[] buckets = new Bucket[10];
            for(int b=0; b<buckets.length; b++) buckets[b] = new Bucket();
            for(int i : a) {
                int lsd = i % ((int)(Math.pow(10, x))) / 10;
                buckets[lsd].add(i);
            }
            int j = 0;
            for(int i=0; i<buckets.length; i++) {
                while(!buckets[i].isEmpty()) {
                    a[j++] = buckets[i].getNext();
                }
            }
        }
    }

Bucket is a class I wrote to help. I think the problem is in the logic that grabs the x-th most significant digit:
Code:
int lsd = i % ((int)(Math.pow(10, x))) / 10; //least significant digit

Is that line correct?


Top
  Profile  
 
 Post subject:
PostPosted: Tue Feb 03, 2009 5:05 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Ugh! I thought I was carrying all of my code with me, but it would seem that I still don't have that figured out....

I need to get that server box going at home so that I can set up SVN and get to my code anywhere. :)

As far as the line you pulled out, I am not sure. it LOOKs okay, but the math/logic is fuzzy in my mind (last time I wrote one was in school, and I never touched it since).


Top
  Profile  
 
 Post subject:
PostPosted: Tue Feb 03, 2009 4:31 pm 
Little Foot
Little Foot
User avatar

Joined: Mon Jul 28, 2008 1:39 pm
Posts: 123
Is it true that Radix sort can be faster than quicksort?


Top
  Profile  
 
 Post subject:
PostPosted: Tue Feb 03, 2009 5:37 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
http://www.jimloy.com/computer/radix.htm
http://www.ddj.com/architect/184405054

Turns out I haven't written a Radix sort. I have written a quick sort though. Seems the general consensus is that the quicksort is faster. For your situation? I don't know.


Top
  Profile  
 
 Post subject:
PostPosted: Tue Feb 03, 2009 5:51 pm 
Little Foot
Little Foot
User avatar

Joined: Mon Jul 28, 2008 1:39 pm
Posts: 123
OK... I still haven't even gotten it to work, so I'm not sure if it's faster.


Top
  Profile  
 
 Post subject:
PostPosted: Tue Feb 03, 2009 8:03 pm 
Willamette
Willamette
User avatar

Joined: Fri Jul 06, 2007 9:29 am
Posts: 1447
It's been a long long time since I did anything with sorting algorithms. I don't remember ever doing a Radix Sort, although I imagine it was in there.

However, in terms of debugging:

1) What are you seeing
2) What are you doing to debug the code?
3) Have you stepped through the code and checked the values after every iteration?
4) Have you stepped through Buckets to see the values after they are all assigned?
5) Have you checked your limits? What assumptions are there on the input values?


Top
  Profile  
 
 Post subject:
PostPosted: Tue Feb 03, 2009 8:19 pm 
Willamette
Willamette
User avatar

Joined: Fri Jul 06, 2007 9:29 am
Posts: 1447
CrashTECH wrote:
Seems the general consensus is that the quicksort is faster. For your situation? I don't know.


Yeah, I looked around at it as well. Looking at it algorithmically, the Quicksort O(n log n) is slower than Radix sort O(n*# of digits in the values) for small values. The advantage goes away as the values and array sizes get larger (pretty much any real world situation).

Real world, you don't get small fixed size integer numbers to sort. Apparently it's the overhead of managing things that also slows down the Radix sort vs Quicksort. Radix sort sure is a lot more work than Quicksort mentally speaking.

Real world, if I am sorting something, I've used Quicksorts 100% of the time. I haven't run into a situation where the time to figure out if another algorithm will give me extra performance was worth it. But that's just me and the programs I have been doing.


Top
  Profile  
 
 Post subject:
PostPosted: Tue Feb 03, 2009 8:43 pm 
Little Foot
Little Foot
User avatar

Joined: Mon Jul 28, 2008 1:39 pm
Posts: 123
Quote:
1) What are you seeing

The algorithm almost sorts the numbers correctly, they are mostly in order, but there are always a few out of place.

Quote:
5) Have you checked your limits? What assumptions are there on the input values?

The numbers to be sorted are all positive integers between 0 and 99.

Working on debugging it...


Top
  Profile  
 
 Post subject:
PostPosted: Tue Feb 03, 2009 10:46 pm 
Willamette
Willamette
User avatar

Joined: Fri Jul 06, 2007 9:29 am
Posts: 1447
What numbers are out of place?
Are the 1 digit numbers sorting intermixed in the two digit numbers? That's a function of the Radix sort from what I saw, it likes the values to all be the same length or it'll mix them together.


Top
  Profile  
 
 Post subject:
PostPosted: Wed Feb 04, 2009 5:53 pm 
Little Foot
Little Foot
User avatar

Joined: Mon Jul 28, 2008 1:39 pm
Posts: 123
Yay! I found the error. My buckets were accidentally implemented as stacks instead of queues, thus ruining the stability that radix sort relies on. But it's fixed now, so everything's fine. :) Thanks for the help and advice guys. And BTW, It's about 10 times slower than quicksort.


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 10 posts ] 

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group