概要

配列のソートアルゴリズムの1つ。

アルゴリズム

ソート対象配列の長さ $n$ の配列について、$i$ 番目の要素を $a_i$ で表す（$i=0,1,2,\cdots,n-1$）。

  1. $i \gets 0$
  2. $a_i,a_{i+1},\cdots,a_{n-1}$ を走査して最小値 $a_j$ を見つける
  3. $a_i$ と $a_j$ の値を交換する
  4. $i \gets i+1$
  5. $i\lt n$ なら2へ戻る。$i=n$ ならソート完了

具体例

順序が確定した要素を <2> のように表す。

[2, 4, 3, 7, 6, 5, 1]
 ^i=0

最小値は a_6=1 なので a_0 と交換して i <- i+1

[<1>, 4, 3, 7, 6, 5, 2]
      ^i=1

i=1 以降の最小値は a_6=2 なので、a_1 と交換して i <- i+1

[<1>, <2>, 3, 7, 6, 5, 4]
           ^i=2

i=2 以降の最小値は a_2=3 なので交換不要。i <- i+1

[<1>, <2>, <3>, 7, 6, 5, 4]
                ^i=3

i=3 以降の最小値は a_6=4 なので、a_3 と交換して i <- i+1

[<1>, <2>, <3>, <4>, 6, 5, 7]
                     ^i=4

i=4 以降の最小値は a_5=5 なので、a_4 と交換して i <- i+1

[<1>, <2>, <3>, <4>, <5>, 6, 7]
                          ^i=5

i=5 以降の最小値は a_5=6 なので交換不要。i <- i+1

[<1>, <2>, <3>, <4>, <5>, <6>, 7]
                               ^i=6

同時に最後の1要素も確定。

[<1>, <2>, <3>, <4>, <5>, <6>, <7>]

--> ソート完了

計算量

時間計算量

  • 外側のループ（最小値を探す走査の開始点を決める）が $O(n)$
  • 内側のループ（最小値を求める）が $O(n)$

なので、時間計算量は $O(n^2)$

空間計算量

元の配列の要素を交換する方式なので、追加のメモリを必要としない。
したがって空間計算量は $O(n)$

実装

テスト：

>>> test_sort_algorithm(SelectionSort())
OK: [1, 6, 2, 7, 5, 4, 3] --> [1 2 3 4 5 6 7]
OK: [2, 4, 3, 7, 6, 5, 1] --> [1 2 3 4 5 6 7]
OK: [3, 1, 5, 7, 6, 4, 2] --> [1 2 3 4 5 6 7]
OK: [3, 6, 5, 7, 4, 2, 1] --> [1 2 3 4 5 6 7]
OK: [4, 3, 7, 6, 5, 2, 1] --> [1 2 3 4 5 6 7]
OK: [5, 2, 1, 7, 6, 4, 3] --> [1 2 3 4 5 6 7]
OK: [5, 7, 2, 6, 4, 3, 1] --> [1 2 3 4 5 6 7]
OK: [6, 4, 3, 7, 5, 2, 1] --> [1 2 3 4 5 6 7]
OK: [7, 2, 5, 6, 4, 3, 1] --> [1 2 3 4 5 6 7]
OK: [7, 6, 5, 4, 3, 2, 1] --> [1 2 3 4 5 6 7]
All 5040 tests passed.

（参考）test_sort_algorithm：指定した長さの全ての組み合わせの配列を生成してソート結果をテストする関数

平均時間計算量 $O(n^2)$ の確認：

Ns = np.arange(1, 10+1) * 1000
ave, std = experiment_computing_time(SelectionSort(), Ns)
draw_computing_order(Ns, ave, std)

selection-sort