並べ替えの対象がたくさんあるとします。その中には同じソート基準を持つものがあります。 numpy.argsort()
は毎回同じ返品を返すと確信できますか?例えばNumpyのargsortは決定的ですか?
、私はargsort([0,0,1])
を呼び出した場合、それが返されます:
[0,1,2]
?[1,0,2]
?ですか?
並べ替えの対象がたくさんあるとします。その中には同じソート基準を持つものがあります。 numpy.argsort()
は毎回同じ返品を返すと確信できますか?例えばNumpyのargsortは決定的ですか?
、私はargsort([0,0,1])
を呼び出した場合、それが返されます:
[0,1,2]
?
[1,0,2]
?
ですか?
これは(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])
しかし、同じ入力与えられ、各ソートアルゴリズムが再び同じ出力を生成します。不安定であっても、与えられたアルゴリズムでラン間を入れ替えて1
と0
をランダムに表示することはありません。不安定性はランダム性を意味するものではなく、同じソートキーを持つ値の入力順が入れ替わる可能性があることを意味します。値がスワップされると、完全に確定的になります。
ソートアルゴリズムに関するWikipediaの記事のstability sectionも参照してください。