diff options
Diffstat (limited to 'numpy')
| -rw-r--r-- | numpy/add_newdocs.py | 2 | ||||
| -rw-r--r-- | numpy/core/fromnumeric.py | 16 | ||||
| -rw-r--r-- | numpy/core/src/multiarray/conversion_utils.c | 4 | ||||
| -rw-r--r-- | numpy/ma/core.py | 4 | ||||
| -rw-r--r-- | numpy/ma/tests/test_core.py | 6 |
5 files changed, 23 insertions, 9 deletions
diff --git a/numpy/add_newdocs.py b/numpy/add_newdocs.py index 316b38e77..0a7b2b13d 100644 --- a/numpy/add_newdocs.py +++ b/numpy/add_newdocs.py @@ -4494,7 +4494,7 @@ add_newdoc('numpy.core.multiarray', 'ndarray', ('sort', axis : int, optional Axis along which to sort. Default is -1, which means sort along the last axis. - kind : {'quicksort', 'mergesort', 'heapsort'}, optional + kind : {'quicksort', 'mergesort', 'heapsort', 'stable'}, optional Sorting algorithm. Default is 'quicksort'. order : str or list of str, optional When `a` is an array with fields defined, this argument specifies diff --git a/numpy/core/fromnumeric.py b/numpy/core/fromnumeric.py index 10256c3c0..63279ffb3 100644 --- a/numpy/core/fromnumeric.py +++ b/numpy/core/fromnumeric.py @@ -764,7 +764,7 @@ def sort(a, axis=-1, kind='quicksort', order=None): axis : int or None, optional Axis along which to sort. If None, the array is flattened before sorting. The default is -1, which sorts along the last axis. - kind : {'quicksort', 'mergesort', 'heapsort'}, optional + kind : {'quicksort', 'mergesort', 'heapsort', 'stable'}, optional Sorting algorithm. Default is 'quicksort'. order : str or list of str, optional When `a` is an array with fields defined, this argument specifies @@ -794,13 +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 - =========== ======= ============= ============ ======= + =========== ======= ============= ============ ======== + 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 @@ -829,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]]) @@ -886,7 +890,7 @@ def argsort(a, axis=-1, kind='quicksort', order=None): axis : int or None, optional Axis along which to sort. The default is -1 (the last axis). If None, the flattened array is used. - kind : {'quicksort', 'mergesort', 'heapsort'}, optional + kind : {'quicksort', 'mergesort', 'heapsort', 'stable'}, optional Sorting algorithm. order : str or list of str, optional When `a` is an array with fields defined, this argument specifies diff --git a/numpy/core/src/multiarray/conversion_utils.c b/numpy/core/src/multiarray/conversion_utils.c index b39834266..7e92e5991 100644 --- a/numpy/core/src/multiarray/conversion_utils.c +++ b/numpy/core/src/multiarray/conversion_utils.c @@ -419,6 +419,10 @@ PyArray_SortkindConverter(PyObject *obj, NPY_SORTKIND *sortkind) else if (str[0] == 'm' || str[0] == 'M') { *sortkind = NPY_MERGESORT; } + else if (str[0] == 's' || str[0] == 'S') { + /* mergesort is the only stable sorting method in numpy */ + *sortkind = NPY_MERGESORT; + } else { PyErr_Format(PyExc_ValueError, "%s is an unrecognized kind of sort", diff --git a/numpy/ma/core.py b/numpy/ma/core.py index 5f53dfdae..91cf8ed0f 100644 --- a/numpy/ma/core.py +++ b/numpy/ma/core.py @@ -5317,7 +5317,7 @@ class MaskedArray(ndarray): originally intended. Until then, the axis should be given explicitly when ``arr.ndim > 1``, to avoid a FutureWarning. - kind : {'quicksort', 'mergesort', 'heapsort'}, optional + kind : {'quicksort', 'mergesort', 'heapsort', 'stable'}, optional Sorting algorithm. order : list, optional When `a` is an array with fields defined, this argument specifies @@ -5468,7 +5468,7 @@ class MaskedArray(ndarray): axis : int, optional Axis along which to sort. If None, the array is flattened before sorting. The default is -1, which sorts along the last axis. - kind : {'quicksort', 'mergesort', 'heapsort'}, optional + kind : {'quicksort', 'mergesort', 'heapsort', 'stable'}, optional Sorting algorithm. Default is 'quicksort'. order : list, optional When `a` is a structured array, this argument specifies which fields diff --git a/numpy/ma/tests/test_core.py b/numpy/ma/tests/test_core.py index 4c6bb2b42..ff1e087b5 100644 --- a/numpy/ma/tests/test_core.py +++ b/numpy/ma/tests/test_core.py @@ -3200,6 +3200,12 @@ class TestMaskedArrayMethods(object): assert_equal(sortedx._data, [1, 2, -2, -1, 0]) assert_equal(sortedx._mask, [1, 1, 0, 0, 0]) + def test_stable_sort(self): + x = array([1, 2, 3, 1, 2, 3], dtype=np.uint8) + expected = array([0, 3, 1, 4, 2, 5]) + computed = argsort(x, kind='stable') + assert_equal(computed, expected) + def test_argsort_matches_sort(self): x = array([1, 4, 2, 3], mask=[0, 1, 0, 0], dtype=np.uint8) |