Comment by yters
17 years ago
Did not realize this: "the median of n integers can be found with just O(n) comparisons."
Must figure this out!
17 years ago
Did not realize this: "the median of n integers can be found with just O(n) comparisons."
Must figure this out!
There are a couple linear-time selection algorithms, some randomized and some not. An example of the latter is described here ( http://www.ics.uci.edu/~eppstein/161/960130.html ). The constant factor is non-trivial here (<= 24n comparisons for this one) but for large datasets it will eventually be faster than sorting.