女性向けエンジニアスクール
3秒でわかる
未整列の範囲から最小値を選んで先頭と入れ替える操作を繰り返す整列法。交換回数が少なく、仕組みが追いやすい入門向けの手法です。
もう少し詳しく
どういうものか
選択ソートは、まだ整列していない範囲の中から最小の要素を選び、その範囲の先頭と入れ替える、という操作を繰り返す整列アルゴリズムです。1周するたびに確定した要素が左に1つ増え、未整列の範囲が1つ縮みます。要素が n 個なら n-1 周で並び終わります。
比較の回数は入力の並びに関係なく常に n(n-1)/2 回で、計算量は O(n^2) です。すでに整列済みのデータを与えても速くなりません。
なぜ必要か
実務で選択ソートを自分で書く場面はほとんどありません。それでも学ぶ価値があるのは、整列の仕組みを追いやすい形をしているからです。ループが二重になり、外側が確定位置、内側が探索範囲、という役割分担がはっきりしていて、計算量が O(n^2) になる理由を数えて確かめられます。
実用面での特徴は、要素の交換が最大でも n-1 回しか起きないことです。要素1個の移動コストが極端に大きい状況では、比較が多くても交換の少ない手法が有利になることがあります。
具体例
def selection_sort(values):
n = len(values)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n): # 未整列の範囲から最小を探す
if values[j] < values[min_index]:
min_index = j
if min_index != i: # 見つかった最小を先頭と交換
values[i], values[min_index] = values[min_index], values[i]
return values
print(selection_sort([64, 25, 12, 22, 11]))1周目 [64, 25, 12, 22, 11] 最小は11 -> [11, 25, 12, 22, 64]
2周目 [11 | 25, 12, 22, 64] 最小は12 -> [11, 12, 25, 22, 64]
3周目 [11, 12 | 25, 22, 64] 最小は22 -> [11, 12, 22, 25, 64]
4周目 [11, 12, 22 | 25, 64] 最小は25 -> そのまま
縦線の左が確定済み。1周ごとに1つずつ確定していくつまずきやすいところ
内側のループを range(i, n) ではなく range(i + 1, n) から始める点を取り違えると、自分自身と比べる無駄が入ります。動作は正しいものの、境界の意味を理解しないまま写すと、応用が利きません。
もうひとつは、最小値そのものを変数に持ってしまう書き方です。値だけ覚えても、どこにあったかが分からないと交換できません。覚えるのは位置（添字）です。
安定性の誤解もあります。選択ソートは離れた位置の要素を直接交換するため、同じ値の要素の前後関係が入れ替わることがあります。名前順に並べたあと点数順に並べ直す、といった二段階の整列では順序が崩れるので、安定な手法を選びます。
似た用語との違い
| 手法 | 平均計算量 | 特徴 |
|---|---|---|
| 選択ソート | O(n^2) | 交換が最少。安定ではない |
| バブルソート | O(n^2) | 隣同士を交換する。安定 |
| 挿入ソート | O(n^2) | ほぼ整列済みなら非常に速い。安定 |
| マージソート | O(n log n) | 常に安定して速い。作業用の領域が要る |
覚え方
手札を並べるとき、残りの中から一番小さいカードを探して左端に置く動きそのものです。
