CODEWITHSUNDEEP
pythonsortingnumpy
user6170905
user6170905

Reputation:

Is Numpy's argsort deterministic?

Let's say I have a bunch of objects to sort, some of them having the same sorting criteria. Can I be certain numpy.argsort() will yield the same return every time ?

For example, If I call argsort([0,0,1]), will it return:

Upvotes: 2

Views: 1836

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1123440

This is documented for the numpy.sort() function (linked from the numpy.argsort() page).

Whether or not the sort is stable depends on the sort algorithm you picked. The default is to use quicksort, and quicksort is not a stable sort. If you must have a stable sort, use kind='mergesort' instead:

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

For your specific example, quicksort returns [0, 1, 2], as does mergesort. Heapsort returns [1, 0, 2] instead:

>>> from numpy import argsort
>>> argsort([0,0,1])
array([0, 1, 2])
>>> argsort([0,0,1], kind='mergesort')
array([0, 1, 2])
>>> argsort([0,0,1], kind='heapsort')
array([1, 0, 2])

However, given the same input, each sort algorithm will produce the same output again. You won't randomly see 1 and 0 swapped between runs with a given algorithm, even if it is an unstable. Instability doesn't imply randomness, it just means that the input order for values with the same sort key could end up being swapped. When values are swapped is entirely deterministic.

Also see the stability section of the Wikipedia article on sorting algorithms.

Upvotes: 9

Related Questions