diff options
| -rw-r--r-- | doc/release/1.15.0-notes.rst | 14 | ||||
| -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 |
6 files changed, 37 insertions, 9 deletions
diff --git a/doc/release/1.15.0-notes.rst b/doc/release/1.15.0-notes.rst index 6e4ef7eed..f5ba2fa38 100644 --- a/doc/release/1.15.0-notes.rst +++ b/doc/release/1.15.0-notes.rst @@ -165,5 +165,19 @@ This change makes it easier to write Python 2/3 compatible code using ``from __future__ import unicode_literals``, which previously would cause string literal field names to raise a TypeError in Python 2. +``sort`` functions accept ``kind='stable'`` +------------------------------------------- +Up until now, to perform a stable sort on the data, the user must do:: + + >>> np.sort([5, 2, 6, 2, 1], kind='mergesort') + [1, 2, 2, 5, 6] + +because merge sort is the only stable sorting algorithm available in +NumPy. However, having kind='mergesort' does not make it explicit that +the user wants to perform a stable sort thus harming the readability. + +This change allows the user to specify kind='stable' thus clarifying +the intent. + Changes ======= 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) |