# Maximum PC

 It is currently Fri Mar 07, 2014 11:26 pm

 All times are UTC - 8 hours

 Page 1 of 1 [ 10 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Problem implementing a Radix sortPosted: Mon Feb 02, 2009 7:43 pm
 Little Foot

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;
}
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

 Post subject: Posted: Tue Feb 03, 2009 5:05 am
 SON OF A GUN

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11602
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

 Post subject: Posted: Tue Feb 03, 2009 4:31 pm
 Little Foot

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

Top

 Post subject: Posted: Tue Feb 03, 2009 5:37 pm
 SON OF A GUN

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11602
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

 Post subject: Posted: Tue Feb 03, 2009 5:51 pm
 Little Foot

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

 Post subject: Posted: Tue Feb 03, 2009 8:03 pm
 Willamette

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

 Post subject: Posted: Tue Feb 03, 2009 8:19 pm
 Willamette

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

 Post subject: Posted: Tue Feb 03, 2009 8:43 pm
 Little Foot

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

 Post subject: Posted: Tue Feb 03, 2009 10:46 pm
 Willamette

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

 Post subject: Posted: Wed Feb 04, 2009 5:53 pm
 Little Foot

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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 10 posts ]

 All times are UTC - 8 hours

#### Who is online

Users browsing this forum: No registered users and 1 guest

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

Search for:
 Jump to:  Select a forum ------------------ Maximum FAQs    Forum Rules, Posting Guidelines & Announcements    The Good, The Bad & The Banned    FAQs Help/Do It Yourself    PC Building Lab    The Help Desk    PC Modding    Education & Certification Hardware    Nuts & Bolts    Portable Talk    Appraisals, Deals & Bargains (oh my!) OS/Software/Programming    Windows Parlor    Alt.OS.Abode    Games Arena    Programmers' Paradise Networking/Internet    Internet Truckstop    Network Nook In/Out    Magazine and Book Feedback    Forum & Website Feedback    Dog Pound Team Maximum PC Folding at Home    Team Maximum PC - Folding at Home - FIND CURES TO DISEASES    Team MPC - Folding Gauntlets