選択ソートとは
選択ソート（Selection Sort）とは、データ群を並び替えるアルゴリズムの一つで、データの中から「最小値（または最大値）」を見つけ出し、それを未整列の部分の先頭と入れ替える操作を繰り返す手法です。「最小値を選択して前に持ってくる」というルールをシンプルに繰り返すことで、配列の左側から順番に整列されたデータが確定していきます。
具体例
トランプのカードがバラバラに置かれているとき、その中から一番数字の小さいカードを目で探して（選択して）一番左側に置きます。次に、残りのカードから一番小さいカードを探してその右隣に置く、という作業を最後の1枚になるまで繰り返す方法です。
# 選択ソートのプログラム例
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i] # 最小値と入れ替えもう少し詳しく
選択ソート（Selection Sort）は、データ群の中から基準となる値（最小値または最大値）を見つけ出し、それを未整列部分の先頭要素と入れ替えることを繰り返すソートアルゴリズムです。昇順ソートの具体的な手順は以下の通りです。まず、配列全体（インデックス0からN-1）の中から最小値を探索します。見つかった最小値と、インデックス0の位置にある要素を入れ替えます。これで、0番目の要素は整列済みとして確定します。次に、残りの範囲（インデックス1からN-1）の中から再び最小値を探し、インデックス1の要素と入れ替えます。この「最小値の探索と確定」を、対象範囲が最後の1要素になるまで繰り返します。このアルゴリズムは、配列の状態（すでに整列しているかどうか）に関わらず、常に N(N-1)/2 回の比較を行うため、最悪・最良・平均いずれの場合も時間計算量は O(N^2) となります。データの入れ替え（スワップ）回数が最大でも N-1 回で済むため、要素の移動コストが非常に高い環境（メモリ書き込みが遅いなど）ではバブルソートより効率的ですが、一般的には低速な部類に入り、またソート後の前後関係が維持されない「不安定ソート」である点に注意が必要です。
試験でのポイント
試験では、選択ソートの比較回数（O(N^2)）や、要素の入れ替え回数（O(N)）の特徴について問われます。また、バブルソートや挿入ソートとの動作の違いを正しく認識しているかが問われるため、「最小値を探し出して、一気に未整列の先頭と交換する」というステップをビジュアル的にトレースできるように整理しておきましょう。不安定ソート（同値のデータの順番が入れ替わる可能性がある）に分類される点も選択肢のポイントとなります。
関連する用語
不安定ソート（同値の要素の順序がソート後に保持されない方式）、比較回数（要素同士の大小判定を行う回数）、交換回数（要素の位置を入れ替える回数）。