Pythonデータサイエンスハンドブック ―Jupyter、NumPy、pandas、Matplotlib、scikit-learnを使ったデータ分析、機械学習

86

2

章 

NumPy

の基礎

In[2]: x = np.array([2, 1, 4, 3, 5])

selection_sort(x)

Out[2]: array([1, 2, 3, 4, 5])

たいていのコンピュータサイエンス専攻の初年度で習うように、選択ソートは単純さの点で有益

ですが、大規模な配列に対する処理時間が大きくなる点に難があります。

N

個の値のリストについ

ては

N

回のループを必要とし、ループのそれぞれで最大

N

回の比較を行い交換対象の値を見つけ

ます。こうしたアルゴリズムを特徴付ける「ビッグオー」記法（囲み「ビッグオー記法」を参照）を使っ

て表すと、選択ソートは

O

[

N

2

]

になります。つまりリスト内の項目数を

2

倍にすると、処理時間

は約

4

倍になります。

それでも選択ソートは、筆者が一番気に入っているソートアルゴリズムであるボゴソートよりは

るかに優れています。

In[3]: def bogosort(x):

while np.any(x[:-1] > x[1:]):

np.random.shuffle(x)

return x

In[4]: x = np.array([2, 1, 4, 3, 5])

bogosort(x)

Out[4]: array([1, 2, 3, 4, 5])

この愚かなソート方法は、完全に偶然に依存しています。結果がソートされるまで、配列のラン

ダムシャッフルを繰り返し行います。このアルゴリズムの計算量は平均で

O

[

N

×

N

!]

（これは

N

×

N

の階乗です）であり、実際の計算に絶対に使用するべきではありません。 ...