ENH: add quickselect algorithm and expose it via partition

A partition sorts the kth element into its sorted order and moves all
smaller elements before the kth element and all equal or greater
elements behind it.
The ordering of all elements in the partitions is undefined.

It is implemented via the introselection algorithm which has worst case
linear complexity compared to a full sort that has linearithmic
complexity.
The introselect algorithm uses a quickselect with median of three pivot
and falls back to a quickselect with median of median of five pivot if
no sufficient progress is made.

The pivots used during the search for the wanted kth element can
optionally be stored and reused for further partitionings of the array.
This is used by the python interface if an array of kth is provided to
the partitions function. This improves the performance of median and
which need to select two elements if the size of the array is even. A
percentile function interpolating between values also profits from this.

String selection is implemented in terms of quicksort which has the same
properties as a selection for now.

1 files changed, 21 insertions, 0 deletions

diff --git a/doc/source/reference/c-api.array.rst b/doc/source/reference/c-api.array.rst
index cef400fad..34ef3318a 100644
--- a/doc/source/reference/c-api.array.rst
+++ b/doc/source/reference/c-api.array.rst
@@ -1810,6 +1810,27 @@ Item selection and manipulation
     would be placed. No checking is done on whether or not self is in
     ascending order.
 
+.. cfunction:: int PyArray_Partition(PyArrayObject *self, PyArrayObject * ktharray, int axis, NPY_SELECTKIND which)
+
+    Equivalent to :meth:`ndarray.partition` (*self*, *ktharray*, *axis*,
+    *kind*). Partitions the array so that the values of the element indexed by
+    *ktharray* are in the positions they would be if the array is fully sorted
+    and places all elements smaller than the kth before and all elements equal
+    or greater after the kth element. The ordering of all elements within the
+    partitions is undefined.
+    If *self*->descr is a data-type with fields defined, then
+    self->descr->names is used to determine the sort order. A comparison where
+    the first field is equal will use the second field and so on. To alter the
+    sort order of a record array, create a new data-type with a different
+    order of names and construct a view of the array with that new data-type.
+    Returns zero on success and -1 on failure.
+
+.. cfunction:: PyObject* PyArray_ArgPartition(PyArrayObject *op, PyArrayObject * ktharray, int axis, NPY_SELECTKIND which)
+
+    Equivalent to :meth:`ndarray.argpartition` (*self*, *ktharray*, *axis*,
+    *kind*). Return an array of indices such that selection of these indices
+    along the given ``axis`` would return a partitioned version of *self*.
+
 .. cfunction:: PyObject* PyArray_Diagonal(PyArrayObject* self, int offset, int axis1, int axis2)
 
     Equivalent to :meth:`ndarray.diagonal` (*self*, *offset*, *axis1*, *axis2*