5 ms·
That second question is kind of dirty. Pretty much all algorithms to find the median will perform a partial sort. Without any sorting at all, the only thing I
by NathanRice 13y ago
That second question is kind of dirty. Pretty much all algorithms to find the median will perform a partial sort. Without any sorting at all, the only thing I can think of is some kind of statistical approximation based on sampling.
- pnathan 13y agoHere's an interesting probabilistic way to sample up to the median: http://blog.aggregateknowledge.com/2013/09/16/sketch-of-the-day-frugal-streaming/ http://blog.aggregateknowledge.com/2013/09/16/sketch-of-the-...