aspose file tools*
The moose likes Java in General and the fly likes Radix Sort Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Radix Sort" Watch "Radix Sort" New topic
Author

Radix Sort

John Lockheart
Ranch Hand

Joined: Oct 13, 2006
Posts: 115
I have a doubly linked circular list class, and a bin class which merely implements methods from the list class, and is itself a list. Inside the bin class is where i need my radix sort method. When radix sorting strings, using the LSD method (least significant digit) i.e. right to left. Where do I begin? Anyone have basic code for dealing with strings that I could examine??
William Brogden
Author and all-around good cowpoke
Rancher

Joined: Mar 22, 2000
Posts: 12803
    
    5
Is there some reason you are not using the sorting methods in the java.util package? They are pretty well optimized for general use.

Are these Strings all ascii characters? Doing a radix sort for a full Unicode character set sounds pretty memory intensive.

Bill
John Lockheart
Ranch Hand

Joined: Oct 13, 2006
Posts: 115
ya, i'm just following a class i'm not actually taking. Were programming all of our own sorts and data structures, and not using any of java's built in stuff. I got the code all figured out now...i'm doing 128 unicode characters, but treating upper and lowercase letters the same when putting them in bins. Each bin contains a Doubly Linked Circular list. When the sort is completed, is it more memory efficient to link the bins all together, then print out the results? Or, pop out all the results in order from each bin into a bin , then print the contents of the newly filled bin? The bins are contained inside an array, so upon initialization ill just create 1 extra bin for the second method i was talking about.
William Brogden
Author and all-around good cowpoke
Rancher

Joined: Mar 22, 2000
Posts: 12803
    
    5
When the sort is completed, is it more memory efficient to link the bins all together, then print out the results? Or, pop out all the results in order from each bin into a bin , then print the contents of the newly filled bin?


I feel sure that iterating through the bins will be more memory efficient than creating yet another data structure. Why the doubly linked list in each bin, do you ever need to interate in the reverse direction?

Years ago I wrote a parser in Java for big text files that was a hybrid of a MSC radix sort plus a Shell sort. The key point for speed and memory efficiency was that it never moved characters or created String objects. Everything was done by moving pointers to word starting characters in the buffer the text was read into treated as one huge character array.

Bill
 
Consider Paul's rocket mass heater.
 
subject: Radix Sort