2016-09-12 14 views
1

並べ替えの対象がたくさんあるとします。その中には同じソート基準を持つものがあります。 numpy.argsort()は毎回同じ返品を返すと確信できますか?例えばNumpyのargsortは決定的ですか?

、私はargsort([0,0,1])を呼び出した場合、それが返されます:

  • [0,1,2]

  • [1,0,2]

  • ですか?

答えて

5

これは(numpy.argsort() pageからリンク)numpy.sort() functionために文書化されています。

ソートが安定しているかどうかは、ソートアルゴリズムを選択したかどうかによって異なります。デフォルトではquicksortを使用し、クイックソートはではなく、安定した並べ替えです。あなたは必見が安定した並べ替えを持って、代わりにkind='mergesort'を使用する場合:あなたの特定例えば

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 

をマージソートがするように、クイックソートは、[0, 1, 2]を返します。ヒープソート代わり[1, 0, 2]を返す:

>>> 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]) 

しかし、同じ入力与えられ、各ソートアルゴリズムが再び同じ出力を生成します。不安定であっても、与えられたアルゴリズムでラン間を入れ替えて10をランダムに表示することはありません。不安定性はランダム性を意味するものではなく、同じソートキーを持つ値の入力順が入れ替わる可能性があることを意味します。値がスワップされると、完全に確定的になります。

ソートアルゴリズムに関するWikipediaの記事のstability sectionも参照してください。

関連する問題