選択ソート(Selection Sort)

ソート基本

選択ソートとは

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

他のソートには計算量が\(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.に戻る

計算量

プログラム上では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での例 (Colaboratory などで確認してみて下さい)

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]

ソート基本

Posted by cs-learner