Hi Neil.

20-May-04 10:49:04, Neil Heller wrote to Jasen Betts


 NH> JB>if you sort the array and then parse it for dupes JB>you can do
 NH> that in O(n)...

 NH> I've never heard of a sorting algorithm working in O(n) time.

radix sort is more of a card trick than a sorting algorithm :)

if ypu were handed a shiffled pack of cards with numbers between 1 and 100
how would you sort them.

radix sort is more of a card trick than a sorting algorithm :)
it dioes the same thing but does it in the opposite order backwards.

here's how it works for input you need a linked list

then you set up an array of 256 other linked lists.

then parse the original list appending takeing the record and appending it
to the list that numbered by the least-significant byte of the integer.

(to efficiently append you need to keep a pointer to both ends of the list,
or better to the last next_element pointer in the list)
( you don't need the list to be linked in both directions)

then join the 255 lists together again into one list and

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

the list is now sorted.

they used to sort punchcards this way but using the value 2 in place of 256

 NH> JB>qsort O(n.log(n)) could be faster than radix sort for small
 NH> arrays.

 NH> Define small?

ISTR my tests indicated qsort was faster for arryas smaller than 3000
entries.

 NH> What is advantageous about radix sort for large arrays?  Does
 NH> large equal everything that's not small?

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

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

 -=> Bye <=-

---