From 4a2891748ab9ac8cafd7aaef10222c761e96f892 Mon Sep 17 00:00:00 2001 From: Lakshay Garg Date: Thu, 29 Mar 2018 12:39:30 +0530 Subject: Remove NPY_STABLESORT enum --- doc/source/reference/c-api.array.rst | 5 ++--- doc/source/reference/c-api.types-and-structures.rst | 5 ++--- numpy/core/fromnumeric.py | 19 +++++++++++-------- numpy/core/include/numpy/ndarraytypes.h | 5 ++--- numpy/core/include/numpy/old_defines.h | 1 - numpy/core/src/multiarray/conversion_utils.c | 3 ++- numpy/core/src/multiarray/item_selection.c | 2 -- 7 files changed, 19 insertions(+), 21 deletions(-) diff --git a/doc/source/reference/c-api.array.rst b/doc/source/reference/c-api.array.rst index 3d0a9e8b8..ad7c725a8 100644 --- a/doc/source/reference/c-api.array.rst +++ b/doc/source/reference/c-api.array.rst @@ -2979,8 +2979,7 @@ to. Convert Python strings into one of :c:data:`NPY_QUICKSORT` (starts with 'q' or 'Q') , :c:data:`NPY_HEAPSORT` (starts with 'h' or 'H'), - :c:data:`NPY_MERGESORT` (starts with 'm' or 'M'), or :c:data:`NPY_STABLESORT` - (starts with 's' or 'S'). + or :c:data:`NPY_MERGESORT` (starts with 'm' or 'M'). .. c:function:: int PyArray_SearchsideConverter( \ PyObject* obj, NPY_SEARCHSIDE* side) @@ -3516,7 +3515,7 @@ Enumerated Types A special variable-type which can take on the values :c:data:`NPY_{KIND}` where ``{KIND}`` is - **QUICKSORT**, **HEAPSORT**, **MERGESORT**, **STABLESORT** + **QUICKSORT**, **HEAPSORT**, **MERGESORT** .. c:var:: NPY_NSORTS diff --git a/doc/source/reference/c-api.types-and-structures.rst b/doc/source/reference/c-api.types-and-structures.rst index 9fb6eb58c..dcebd1ede 100644 --- a/doc/source/reference/c-api.types-and-structures.rst +++ b/doc/source/reference/c-api.types-and-structures.rst @@ -551,9 +551,8 @@ PyArrayDescr_Type An array of function pointers to a particular sorting algorithms. A particular sorting algorithm is obtained using a key (so far :c:data:`NPY_QUICKSORT`, :c:data:`NPY_HEAPSORT`, - :c:data:`NPY_MERGESORT`, and :c:data:`NPY_STABLESORT` are - defined). These sorts are done in-place assuming contiguous - and aligned data. + and :c:data:`NPY_MERGESORT` are defined). These sorts are done + in-place assuming contiguous and aligned data. .. c:member:: int argsort( \ void* start, npy_intp* result, npy_intp length, void *arr) diff --git a/numpy/core/fromnumeric.py b/numpy/core/fromnumeric.py index ddf3314cf..63279ffb3 100644 --- a/numpy/core/fromnumeric.py +++ b/numpy/core/fromnumeric.py @@ -794,14 +794,13 @@ def sort(a, axis=-1, kind='quicksort', order=None): order. The three available algorithms have the following properties: - =========== ======= ============= ============ ======= - kind speed worst case work space stable - =========== ======= ============= ============ ======= - 'quicksort' 1 O(n^2) 0 no - 'mergesort' 2 O(n*log(n)) ~n/2 yes - 'stable' 2 O(n*log(n)) ~n/2 yes - 'heapsort' 3 O(n*log(n)) 0 no - =========== ======= ============= ============ ======= + =========== ======= ============= ============ ======== + kind speed worst case work space stable + =========== ======= ============= ============ ======== + 'quicksort' 1 O(n^2) 0 no + 'mergesort' 2 O(n*log(n)) ~n/2 yes + 'heapsort' 3 O(n*log(n)) 0 no + =========== ======= ============= ============ ======== All the sort algorithms make temporary copies of the data when sorting along any but the last axis. Consequently, sorting along @@ -830,6 +829,10 @@ def sort(a, axis=-1, kind='quicksort', order=None): heapsort when it does not make enough progress. This makes its worst case O(n*log(n)). + 'stable' automatically choses the best stable sorting algorithm + for the data type being sorted. It is currently mapped to + merge sort. + Examples -------- >>> a = np.array([[1,4],[3,1]]) diff --git a/numpy/core/include/numpy/ndarraytypes.h b/numpy/core/include/numpy/ndarraytypes.h index 5febf0c56..cf73cecea 100644 --- a/numpy/core/include/numpy/ndarraytypes.h +++ b/numpy/core/include/numpy/ndarraytypes.h @@ -159,10 +159,9 @@ enum NPY_TYPECHAR { typedef enum { NPY_QUICKSORT=0, NPY_HEAPSORT=1, - NPY_MERGESORT=2, - NPY_STABLESORT=3 + NPY_MERGESORT=2 } NPY_SORTKIND; -#define NPY_NSORTS (NPY_STABLESORT + 1) +#define NPY_NSORTS (NPY_MERGESORT + 1) typedef enum { diff --git a/numpy/core/include/numpy/old_defines.h b/numpy/core/include/numpy/old_defines.h index 6d626aa2a..abf81595a 100644 --- a/numpy/core/include/numpy/old_defines.h +++ b/numpy/core/include/numpy/old_defines.h @@ -134,7 +134,6 @@ #define PyArray_QUICKSORT NPY_QUICKSORT #define PyArray_HEAPSORT NPY_HEAPSORT #define PyArray_MERGESORT NPY_MERGESORT -#define PyArray_STABLESORT NPY_STABLESORT #define PyArray_SORTKIND NPY_SORTKIND #define PyArray_NSORTS NPY_NSORTS diff --git a/numpy/core/src/multiarray/conversion_utils.c b/numpy/core/src/multiarray/conversion_utils.c index bf60fba7f..7e92e5991 100644 --- a/numpy/core/src/multiarray/conversion_utils.c +++ b/numpy/core/src/multiarray/conversion_utils.c @@ -420,7 +420,8 @@ PyArray_SortkindConverter(PyObject *obj, NPY_SORTKIND *sortkind) *sortkind = NPY_MERGESORT; } else if (str[0] == 's' || str[0] == 'S') { - *sortkind = NPY_STABLESORT; + /* mergesort is the only stable sorting method in numpy */ + *sortkind = NPY_MERGESORT; } else { PyErr_Format(PyExc_ValueError, diff --git a/numpy/core/src/multiarray/item_selection.c b/numpy/core/src/multiarray/item_selection.c index 0ee6c8184..eb9ef5915 100644 --- a/numpy/core/src/multiarray/item_selection.c +++ b/numpy/core/src/multiarray/item_selection.c @@ -1130,7 +1130,6 @@ PyArray_Sort(PyArrayObject *op, int axis, NPY_SORTKIND which) case NPY_HEAPSORT: sort = npy_heapsort; break; - case NPY_STABLESORT: case NPY_MERGESORT: sort = npy_mergesort; break; @@ -1282,7 +1281,6 @@ PyArray_ArgSort(PyArrayObject *op, int axis, NPY_SORTKIND which) case NPY_HEAPSORT: argsort = npy_aheapsort; break; - case NPY_STABLESORT: case NPY_MERGESORT: argsort = npy_amergesort; break; -- cgit v1.2.1