From 9c4c1c432b27f67eee2ad22ff5f2f9833bd1516d Mon Sep 17 00:00:00 2001 From: Julian Taylor Date: Sat, 18 May 2013 07:45:04 +0200 Subject: 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. --- doc/source/reference/c-api.array.rst | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) (limited to 'doc/source/reference/c-api.array.rst') 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* -- cgit v1.2.1