
A.6
ソートについてさらに詳しく
517
の違いを気にする場面は少ないことと思いますが、違いがあることを知っておく価値はあります。
表A-3 配列のソートメソッド
種類 速度 安定性 作業領域 最悪の計算量
'quicksort'
1
不安定
0
O(n^2)
'mergesort'
2
安定
n / 2 O(n log n)
'heapsort'
3
不安定
0
O(n log n)
A.6.3
配列の一部分をソートする
時として、配列内で最も大きな要素や最も小さな要素いくつかを決定するためにソートを行うことが
あります。
NumPy
には、このような用途に最適化されたメソッド
numpy.partition
と
np.argpartition
があります。これらのメソッドを使うと、配列内で最も小さな要素
k
個を取り出すことが可能です。
In [194]: np.random.seed(12345)
In [195]: arr = np.random.randn(20)
In [196]: arr
Out[196]:
array([-0.2047, 0.4789, -0.5194, -0.5557, 1.9658, 1.3934,
0.0929,
0.2817, 0.769 , 1.2464, 1.0072, -1.2962, 0.275 , 0.2289,
1.3529, 0.8864, -2.0016, -0.3718, 1.669 , -0.4386])
In [197]: np.partition(arr, 3)
Out[197]: ...