> I've never seen an algorithm for sorting that's better than
> O(n log n) on average. Are there any? I can't even imagine
> how a sort could possibly be done in O(n) time, since that
> would require looking at
All the algorithms I've seen for sorting in less than O(n log n)
have required knowledge of your data-set's features. The O(n log
n) family of sorts involve comparisons, where this is the lower
bound. Using methods other than comparison for sorting is where
you jump to O(n) with your counting/radix/bucket sorts. This
usually involves knowing the upper/lower bounds of the data, the
number of items to be sorted, and/or the distribution within them.
My copy of _Introduction to Algorithms_ (by Cormen, Leiserson,
and Rivest) has an entire chapter (#9) on "Sorting in linear
time" that introduces all three of the aforementioned algorithms
with sample pseudo-code implementations for each.
The counting sort uses the actual elements as indicies, such as a
sorting a shuffled deck of cards:
destination = Card[4][13]
for card in shuffled(cards):
dest[card.suit][card.rank] = card
Radix & bucket sorts are a bit more complex, but aren't bad. I
believe the radix sort is O(N * D) (where N="number of items" and
D="number of digits/length-of-string"), and the bucket sort is
O(N * C) where N="number of items" and C="degree of
collision/commonality" (so if you have a lot of data that has the
same keys for your buckets, you'll actually get *worse*
performance due to the collisions). They both presume that D/C
are fairly small and constant for your data-set.
-tim
--~--~---------~--~----~------------~-------~--~----~
You received this message from the "vim_use" maillist.
For more information, visit http://www.vim.org/maillist.php
-~----------~----~----~----~------~----~------~--~---
