(1) 選択ソート（単純選択法）
選択ソート（単純選択法）とは
選択ソート（単純選択法）は、配列の中から最小の要素を見つけて、先頭に移動させることを繰り返すことでソートするアルゴリズムです。
手順
- 整列していない配列（リスト）を用意します。
- 未整列の先頭の値を暫定の最小値とします。
- 未整列部分の2番目から末尾までを調べ、最小値の位置を記録します。
- 未整列の先頭と、見つけた最小値の位置が異なる場合は交換し、未整列の先頭を整列済みにします。
- (2)〜(4)を繰り返し、すべての値が整列済みになれば終了します。
デモンストレーション
プログラム
Colaboratoryのノートブックに書き写しながら、理解しましょう。
arr = [6, 3, 2, 0, 7, 1, 4, 5] # 元のリスト
print(arr) # ソート前を出力
n = len(arr)
print("------------------------")
for i in range(n - 1): # 未整列の左端を1つずつ後にずらしていく（繰り返しインデックスの変数をiとする）
min_index = i # 暫定最小値の位置（初期値は未整列の先頭のインデックス=i）
for j in range(i + 1, n): # 未整列部分の2番目(i+1)から末尾まで繰り返す（繰り返しインデックスの変数をjとする）
if arr[min_index] > arr[j]: # 暫定最小値よりもインデックス番号jの値が小さければ、
min_index = j # 暫定最小値の位置をインデックス番号jとする
# この時点で、未整列の最小値がarr[min_index]と決まる
if min_index != i: # インデックス番号iの要素と未整列の最小値を交換する
tmp = arr[min_index]
arr[min_index] = arr[i]
arr[i] = tmp
print(arr) # 途中経過を出力
print("------------------------")
print(arr) # ソート後を出力
[6, 3, 2, 0, 7, 1, 4, 5]
------------------------
[0, 3, 2, 6, 7, 1, 4, 5]
[0, 1, 2, 6, 7, 3, 4, 5]
[0, 1, 2, 6, 7, 3, 4, 5]
[0, 1, 2, 3, 7, 6, 4, 5]
[0, 1, 2, 3, 4, 6, 7, 5]
[0, 1, 2, 3, 4, 5, 7, 6]
[0, 1, 2, 3, 4, 5, 6, 7]
------------------------
[0, 1, 2, 3, 4, 5, 6, 7]
関連項目
・4-1. リニアサーチ（線形探索法） 最小値探索のプログラム
このアルゴリズムの特徴
比較回数
最初に、\(n-1\) 回の比較を行って、最小値を探します。次に、残りの未整列要素 \(n-2\) 個の最小値を探すために \(n-2\) 回の比較を行います。よって、
\[ 比較回数 = (n-1) + (n-2) + (n-3) + \cdots + 2 + 1 = \frac{1}{2}n(n-1) \]となります。
交換回数
未整列部分の最小値の位置が未整列の先頭と異なる場合に、1回交換します。よって、最大交換回数は \(n-1\) 回となります。
バブルソートとの比較
比較回数はどちらのアルゴリズムも同じ回数ですが、最大交換回数は選択ソートの方が小さくなるので、バブルソートよりは少しだけ速くなります。しかし、どちらのアルゴリズムも高効率とはいえず、次ページ以降のアルゴリズムがよく用いられます（プログラミングの学習としては、バブルソートや選択ソートは最適です）。