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??
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.
Joined: Oct 13, 2006
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.
Author and all-around good cowpoke
Joined: Mar 22, 2000
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.