• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Radix Sort

 
Ranch Hand
Posts: 117
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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??
 
Author and all-around good cowpoke
Posts: 13078
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 117
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 13078
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic