ソートは基本的な操作でありながら、コンピュータが実行すべき最も重要な操作の1つである。
これは、検索やマージなど、他の多くのアルゴリズムや手順の構成要素です。
さまざまなソートアルゴリズムを知ることは、異なるアルゴリズムの背後にある考え方をよりよく理解し、よりよいアルゴリズムを考え出すのに役立つだろう。
選択ソートアルゴリズムは、ソートされていない部分の最小値を求め、それを最初のソートされていない要素と入れ替えることで配列をソートします。
これはインプレースアルゴリズムであり、追加のリストを割り当てる必要がないことを意味する。
低速ではありますが、メモリに制限のあるシステムにおいて、メインのソートアルゴリズムとして使用されています。
この記事では、選択ソートがどのように動作するかを説明し、Pythonでそれを実装します。
そして、アルゴリズムの動作を分解して、その時間複雑性を学びます。
選択ソート
では、選択ソートはどのように動作するのでしょうか。
選択ソートは入力リストを2つの部分に分割します。
最初は空のソートされた部分と、最初はすべての要素のリストを含む未ソート部分です。
そして、ソートされていないファイルの中から最小値を選び、それを最初のソートされていない値と交換し、ソートされた部分を1つ増やします。
このソートの高レベル実装は次のようなものである。
def selection_sort(L):
for i in range(len(L) - 1):
min_index = argmin(L[i:])
L[i], L[min_index] = L[min_index], L[i]
上の擬似コードにおいて、argmin() は最小値のインデックスを返す関数である。
このアルゴリズムでは、変数 i を使って、ソートされたリストがどこで終わり、ソートされていないリストがどこで始まるかを記録しています。
ソートされていない項目から始めて最小値を取るので、ソートされていない部分のすべてのメンバがソートされている部分のどのメンバよりも大きいということが常に起こります。
最初の行では i の値を増加させ、2番目の行では最小値のインデックスを見つけ、3番目の行ではそれらの値を入れ替えています。
Pythonは左辺に何かを代入する前に右辺を計算するので、一時的な変数は必要ありません。
次の要素を含むリストで、実際にどのように動作するかを見てみましょう。
まず、ソートされていないリストから始めます。
- 3 5 1 2 4
ソートされていない部分には、すべての要素があります。
各項目に目を通し、1が最も小さい要素であると判断します。
そこで、1と3を入れ替えます。
- 1 5 3 2 4
残りのソートされていない要素 [5, 3, 2, 4] のうち、2 が最も小さい数です。
ここで、2と5を入れ替えます。
- 1 2 3 5 4
この処理は、リストがソートされるまで続けられます。
- 1 2 3 5 4
- 1 2 3 4 5
- 1 2 3 4 5
では、これをPythonでどのように実装するか見てみましょう。
実装
このアルゴリズムを実装するコツは、最小値を記録しておくことと、リストの2つの要素を入れ替えることです。
お気に入りのエディタで sort.py というファイルを開き、以下のコードを入力します。
def selection_sort(L):
# i indicates how many items were sorted
for i in range(len(L)-1):
# To find the minimum value of the unsorted segment
# We first assume that the first element is the lowest
min_index = i
# We then use j to loop through the remaining elements
for j in range(i+1, len(L)-1):
# Update the min_index if the element at j is lower than it
if L[j] < L[min_index]:
min_index = j
# After finding the lowest item of the unsorted regions, swap with the first unsorted item
L[i], L[min_index] = L[min_index], L[i]
では、このファイルにアルゴリズムをテストするためのコードを追加してみましょう。
L = [3, 1, 41, 59, 26, 53, 59]
print(L)
selection_sort(L)
# Let's see the list after we run the Selection Sort
print(L)
そしてターミナルを開いて実行すると、結果を見ることができます。
$ python sort.py
[3, 1, 41, 59, 26, 53, 59]
[1, 3, 26, 41, 53, 59, 59]
リストは正しくソートされました。
これで、Pythonで選択ソートを実装できることがわかりました。
それでは、理論的な部分と、時間に関するパフォーマンスを見てみましょう。
時間的な複雑さの計算
では、選択ソートはどれくらいの時間をかけてリストを並べ替えるのでしょうか？ここでは、サイズ n の配列に対して、選択ソートアルゴリズムがどれくらいの時間を要するかを正確に計算するアプローチを取ります。
def selection_sort(L):
この行は関数スタックをセットしているだけなので、それほど時間はかからないはずです。
これは定数と呼ばれるもので、入力の大きさが変わっても、このコードが実行される時間は変わりません。
この行を実行するのに、c1回の演算が必要だとしましょう。
次に、次のようになります。
for i in range(len(L)-1):
これは少し難しい。
まず、forループが始まる前に len() と range() という2つの関数を呼び出しています。
Windows、Linux、MacのPythonのデフォルト実装であるCPythonでは、 len() のコストもサイズに依存しないようになっています。
これは range() の初期化にも当てはまります。
この2つを合わせて c2 と呼ぶことにしましょう。
次に for ですが、これは n - 1 回実行されます。
これは定数ではなく、入力の大きさによって実行される時間が変わります。
つまり、1つのループが完了するまでにかかる時間を n - 1 倍にしなければなりません。
in演算子を評価するための定数コスト、仮にc3` とします。
これは外側のforループをカバーするものです。
変数の代入も定数時間で行われます。
これを c4 と呼ぶことにします。
min_index = i
今度は内側のループです。
これは2つの定数関数を呼び出すものです。
これらは c5 の操作を要するとしましょう。
c5はc2とは異なることに注意してください。
なぜなら、ここでのrange` は引数を2つ持っており、ここでは加算演算が行われているからです。
ここまでで、c1 + c2 + (n - 1) * (c3 + c4 + c5) の演算を行い、内部ループが始まり、すべてを掛け算している…？さて、トリッキーですが、よく見ると、最初のループでは n - 2 回、2回目では n - 3 回、最後では 1 回を要しています。
全てに1からn - 2までの全ての数値の和を掛ける必要があるのです。
数学者は、その和は (n - 2) * (n - 1) / 2 であると言っています。
1 から任意の正の数 x までの整数の和について、詳しくはこちらをご覧ください。
内部ループの内容も同様に一定時間で完了する。
Pythonが in, if, 代入文と変数の入れ替えを行うのにかかる時間を、任意の定数時間 c6 に割り当ててみましょう。
for j in range(i+1, len(L)-1):
if L[j] < L[min_index]:
min_index = j
L[i], L[min_index] = L[min_index], L[i]
全部で c1 + c2 + (n - 1) * (c3 + c4 + c5) + (n - 2) * (n - 3) * c6 / 2 が得られます。
これを単純化すると a * n * n + b * n + c, ここでa,b,c` は評価される定数の値を表します。
これは O(n2) として知られています。
どういうことでしょうか？要約すると、このアルゴリズムの性能は入力リストのサイズの2乗に基づくということです。
したがって、もしリストの大きさを2倍にすれば、ソートにかかる時間は4倍になります。
入力の大きさを3で割れば、時間は9倍短縮されます。
結論
この記事では、選択ソートがどのように機能するかを調べ、Pythonでそれを実装しました。
そして、そのコードを一行ずつ分解して、アルゴリズムの時間複雑性を分析しました。
ソートアルゴリズムを学ぶことは、一般的なアルゴリズムに対する理解を深めることにつながります。