[Numpy-discussion] algorithm for faster median calculation ?

[Sturla Molden]

On 15.01.2013 20:50, Sturla Molden wrote:
> You might want to look at this first:
>
> https://github.com/numpy/numpy/issues/1811
>
> Yes it is possible to compute the median faster by doing quickselect
> instead of quicksort. Best case O(n) for quickselect, O(n log n) for
> quicksort. But adding selection and partial sorting to NumPy is a bigger
> issue than just computing medians and percentiles faster.


Anyway, here is the code, a bit updated.

I prefer quickselect with a better pivot though.

Sturla
-------------- next part --------------
A non-text attachment was scrubbed...
Name: median.py
Type: text/x-python
Size: 5604 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20130115/72c1d727/attachment.py>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: quickselect.pyx
Type: /
Size: 3346 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20130115/72c1d727/attachment.bin>