3 ms·
> The question was basically, "Find the median of a huge data set without sorting it," [...] You can use eg QuickSelect (https://en.wikipedia.org/wiki/Quicksel
by eru 5y ago
> The question was basically, "Find the median of a huge data set without sorting it," [...]
You can use eg QuickSelect (https://en.wikipedia.org/wiki/Quickselect https://en.wikipedia.org/wiki/Quickselect) or Median of Medians.
They don't sort the data, but they do need linear amount of storage.