Hi Neil.

22-May-04 10:33:00, Neil Heller wrote to Jasen Betts


 NH> JB>then join the 255 lists together again into one list and

 NH> JB>repeat using the next least significant byte, JB>repeat unitl
 NH> all bytes of the key value have been used,

 NH> JB>the list is now sorted.

 NH> Ahhh... Radix sort now comes back to me.

 NH> JB>AFAIK there's nothing more efficient than O(n) sorting. JB>but
 NH> remember you do need memory for the linked list

 NH> JB>it's possible with a few tweaks do radix sort on IEEE floating
 NH> point JB>numbers too, but it'll never work for strings etc...

 NH> It seems to me that if Radix sort works correctly with multi-byte
 NH> integers and floats, it should work with strings.

It will work for fixed-length strings.
the longer the strings the more steps are needed to sort them. (it'll work
for nul-padded strings too, also for nul-terminated (as long as the length
is limited) and as long as having the having the data ordered by the
garbage bytes in cases when the strings match isn't an issue)

 NH> Why won't it?

 1. handling variable-length strings is messy you start at the
    nth position and work back to the first...

 2. it works best for large lists that fit into memory, when strings are
    involved often there's not room to hold enough data to have it outpreform
    qsort on an array of pointers

I think mainly those two points.

 OTOH there may be a way to turn it on its head so that it can be applied
 to strings

 a sort of 'division' sort where the input data is divided into 256 buckets
according to the first character, and then each of those buckets is
subjected to the same division process based on the next character....
it seesm to me that that algorithm could require large amounts of memory

   sizeof (pointer)*256*{longest_string_match}

 -=> Bye <=-

---