Jeff 'japhy' Pinyan wrote: > Ooh, radix sort. This is a cool technique, but it has a drawback: it > always runs in the same time. Sorting sorted data takes as long as > sorting UNsorted data. (Or sordid data!)
I love the implementation, gotta examine it closely and your example by hand with your code. Thanks! I got this from http://www.wikipedia.com/wiki/Radix_sort: QUOTE Radix sort is a sort algorithm that operates in O(n) time. This algorithm was orignally used to sort punched cards in several passes. It has resurfaced as an alternative to other high performance sorting algorithms (like quicksort, heapsort and merge sort) which run in O(n lg n)) time. Its greatest disadvantages are that it usually cannot be made to run in place, so O(n) additional memory space is needed, and that it requires one pass for each symbol of the key, so it is very slow for potentially-long keys. /QUOTE I taught all sorts of sorts (oh dear, sorry about that one!) to my AP C++ students, and they were astounded by how fast radix was compared to the other "good" sorts. Of course, we were using randomized data at the time. It seems to me if you have some knowledge that the data is unsorted or random, it might be to your advantage to run the radix algorithm instead. Thoughts? Anyone done some testing on actual data? What's that timing module again? Pete -- Mynd you, møøse bites Kan be pretty nasti... -- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
