(1) 選択ソート（単純選択法）
選択ソート（単純選択法）とは
選択ソート（単純選択法）は、配列の中から最小の要素を見つけて、先頭に移動させることを繰り返すことでソートするアルゴリズムです。
手順
- 整列していない配列（リスト）を用意します。
- 未整列の先頭の値を暫定の最小値とします。
- 未整列の２番目から末尾までの最小値を探し、暫定の最小値よりも小さければ、未整列の先頭と交換します。
- 未整列の先頭を整列済みにします。
- (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): # 未整列の２番目(i+1)から末尾まで繰り返す（繰り返しインデックスの変数をjとする）
if arr[min_index] > arr[j]: # 暫定最小値よりもj番目の値が小さければ、
min_index = j # 暫定最小値の位置をj番目とする
# この時点で、未整列の最小値がarr[min_index]と決まる
tmp = arr[min_index] # i番目(arr[i])と未整列の最小値(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\) 回となります。
バブルソートとの比較
比較回数はどちらのアルゴリズムも同じ回数ですが、最大交換回数は選択ソートの方が小さくなりますので、バブルソートよりは少しだけ速くなります。しかし、どちらのアルゴリズムも高効率とはいえず、次ページ以降のアルゴリズムがよく用いられます（プログラミングの学習としては、バブルソートや選択ソートは最適です）。