選択ソート(Selection Sort)

2019年11月22日ソート基本

選択ソートとは

ソートアルゴリズムの中でも、最も基本的なアルゴリズムの一つです。配列の中から最小値や最大値を探して、先頭や最後尾と入れ替えながらソートしていきます。

他のソートには計算量が \(O(nlogn)\) のものもありますが、選択ソートの計算量は \(O(n^2)\) となっています。

しかし、アルゴリズムが簡単なので、遅くても使われることがあります。

通常の選択ソートは安定ソート(Stable Sort) ではありませんが、アルゴリズムの一部を変更することで安定ソートにすることができます。

アルゴリズム

以下のように最小の要素を見つけて、配列の先頭と入れ替えることを続けます。

  1. \(i=0\) とする
  2. \(i\) 番目から配列の最後尾まで全ての要素を確認し、最小の要素と \(i\) 番目の要素を入れ替える
  3. \(i\) を 1 増やして、\(i\) が配列の長さ以上だったら終了。そうでなければ 2. に戻る

ここでの2.のように「最小の要素と\(i\)番目の要素を入れ替える」とすると安定ではないソート、「最小の要素を\(i\)番目の要素の前に挿入して、他を前に1つずつずらす」に変更すると安定ソートになります。

最小の要素をみつけるためには、以下のアルゴリズムを用いれば良いです。

  1. \(j=i\) とする
  2. \(i\) 番目から \(j\) 番目までで見つけた最小の要素とそのindexを覚えておき、\(j+1\) 番目がそれより小さいかどうかを比較する
  3. \(j\) を 1 増やして、\(j\) が配列の長さ以上だったら現在保持している最小の要素のindexを返して終了
  4. そうでなければ 2. に戻る

計算量

  • \(O(n^2)\)

配列の要素数を n とすると、最小値を見つけて要素を交換するのに平均 n 回比較を行い、0 番目から n-1 番目までこれを繰り返すので、計算量は \(O(n^2)\) となります。（プログラム上では２重のループで記述できます。）

計算量の詳しい説明

比較回数は、\(i\)番目から配列の最後尾まで確認するために \(n-i-1\) 回必要です。また、この時の交換回数は 0 か 1 回です。

これが、\(i\) が \(0\) から \(n-1\) のときまで繰り返されるので、比較回数の総和は

$$ \sum_{i=0}^{n-1} (n-i-1) = \frac{n(n-1)}{2}$$

となります。また、交換回数の総和は多くても \(n-1\) 回。

以上から、オーダー記法を用いると、計算量は \(O(n^2)\) とわかります。

Pythonでのプログラム例

def selection_sort(arr):
  for i in range(len(arr)):
    min_value = arr[i]
    min_index = i
    for j in range(i, len(arr)): # ループで最小の要素を確認する
      if arr[j] < min_value:
        min_value = arr[j]
        min_index = j
    # 要素の入れ替え、arr[i],arr[min_index] = arr[min_index],arr[i] としてもよい
    tmp = arr[i]
    arr[i] = arr[min_index]
    arr[min_index] = tmp

arr = [3,1,55,2,28,19,31,93,6]
selection_sort(arr)
print(arr)  # 出力は[1, 2, 3, 6, 19, 28, 31, 55, 93]

(Colaboratory などで確認してみて下さい）

ソート基本