選択ソートとは？せんたくそーと
選択ソートとは、まだ並べていない範囲から最小（または最大）の値を探し、その範囲の先頭と入れ替える操作を繰り返してデータを整列する方法である。n個の要素なら比較はn(n-1)/2回で、データがどう並んでいても変わらない。入れ替えは各回1度だけなので最大n-1回で済み、この「比較は多いが交換は少ない」性質がバブルソートとの対比で問われる。
最終更新：2026-10-09
基本情報を最短で暗記・合格する →背景
並べ替えの最も素朴な考え方は「一番小さいものを探して先頭に置く」で、選択ソートはそれをそのまま手順にしたものである。実用の速さでは劣るが、動作が単純で計算量を数えやすいため、科目Bのアルゴリズム問題で「比較回数」「入れ替え回数」「i回目終了時の配列」を追わせる素材として定番になっている。
具体例
テストの点数[72,45,91,38]を昇順にする。全体の最小38を先頭の72と交換して[38,45,91,72]、残り3つの最小45はすでに2番目なので交換なし、残り2つの最小72を91と交換して[38,45,72,91]。比較は3+2+1=6回、交換は2回。Pythonならmin()と入れ替えの数行で書ける。
試験での引っ掛け
「整列済みのデータなら比較が減る」は誤りで、選択ソートは並びに関係なく毎回全走査するため最良も最悪もO(n²)（データが2倍なら時間は4倍）。途中で打ち切る工夫ができるバブルソートとの違いがここ。また離れた要素を直接交換するため、同じ値の並び順が入れ替わりうる不安定なソートである。
関連用語
出典・参考
公式シラバスの1 基礎理論 ＞ 2. アルゴリズム ＞ (2) 代表的なアルゴリズムに掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。