I apologize in advances if this is the wrong place to be asking this question, (I had considered putting it on CV first).

I am studying financial (S&P, Dow Jones, etc) data, and would like to compute some quantiles of an array of numbers. I have been reading about quantiles, so I know what they are, but does the computation of quantiles ALWAYS mean that I need to sort my data first? Or are there methods where quantiles can be computed without first sorting your array of numbers?

Thank you.


You don't need to sort your data first, if you have access to additional temporary storage, in which case, you should use a selection algorithm.

  • $\begingroup$ Thanks Geoff. I didn't even know where to start looking, this is very helpful. Based on the wiki, kth-order statistics (KOS) are thus generalizations of quantiles, and thus arbitrary quantiles can be computed using selection algorithms that do not use any type of sorting? $\endgroup$ Dec 20 '13 at 0:05
  • $\begingroup$ Generally speaking, yes. The median might not be an order statistic, for instance, if you have an even number of samples, but in many cases, it is. Similar caveats apply to other order statistics. $\endgroup$ Dec 20 '13 at 0:35

Your Answer

