選択ソートの対象試験と出題頻度
選択ソートは名前が地味なうえ、バブルソートや挿入ソートと記憶が混ざりやすい手法です。試験対策としてどこまで踏み込むべきか、迷う受験者も多いのではないでしょうか。
出題の主戦場はFE・APの科目A(午前)。
選択ソートが正解として問われるのは、ほぼ「比較回数の式を答える計算問題」に限られます。一方で、クイックソートやバブルソートを主題とする設問の誤答選択肢としては頻繁に顔を出す。
7手法の全体像は整列アルゴリズム(ソート)の記事で確認してください。
出題情報を確認する
基本情報技術者(FE) 応用情報技術者(AP)
★★★☆☆
ランクB(標準)/科目Aの計算問題で正解、他手法の設問では誤答選択肢として登場
選択ソート(基本選択法)の定義
選択ソートという名前だけを見ても、何を「選択」しているのかは伝わってきません。選ばれているのは、未整列部分に残っている最小値(または最大値)です。
別名が多いのも混乱の原因で、基本選択法・単純選択法と呼ばれるほか、大きい順に並べる版は最大値選択法と呼ばれます。IPAの問題文では手法名を出さず、流れ図や文章で動きだけを示す形が主流。
選択ソートとは、
「未整列部分から最小値を探し、未整列部分の先頭要素と交換することを繰り返す整列法」
です。
朝礼の整列を思い浮かべてみてください。
全員の身長を見比べて一番低い人を先頭に呼び出し、次は残った人の中から一番低い人を呼ぶ。この「毎回まとめて探してから1回だけ動かす」流れが選択ソートの正体です。
📊 選択ソートの基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Selection Sort |
| 別名 | 基本選択法/単純選択法/最大値選択法(降順版) |
| 分類 | テクノロジ系 / アルゴリズム / 整列アルゴリズム |
| 比較回数 | 常に n(n-1)/2 回(データの並び順に依存しない) |
| 交換回数 | 最大 n-1 回(1パスあたり1回以下) |
| 計算量 | 最良・平均・最悪すべて O(n²) |
| 安定性 | 不安定 |
解説:最小値を1つ選んで先頭に置く仕組み
1パスの動きを4ステップで追う
1パスの処理は4つのステップに分解できます。注目すべきは、交換がパスの最後に1回しか発生しない点。
配列 (4, 1, 3, 2) を昇順に整列する1パス目を、実際の値付きで並べます。
選択ソート1パスの計算手順(配列 4, 1, 3, 2)
min ← A[1]=4
1<4 で min ← A[2]
(比較3回)
4 ⇄ 1 →(1, 4, 3, 2)
次は A[2]〜A[4]
探索(②)は毎回フル、交換(③)は1回だけ。この非対称が回数の式に直結する
FE科目B対策として、同じ処理を擬似言語でも見ておきましょう。
内側ループが最小値の位置を探し、交換は外側ループの中で1回だけ行われる構造になっています。
○選択ソート(整数型の配列: data)
整数型: i, j, min, tmp
for (i を 1 から dataの要素数 - 1 まで 1 ずつ増やす)
min ← i /* ①候補を仮置き */
for (j を i + 1 から dataの要素数 まで 1 ずつ増やす)
if (data[j]
配列 (4, 1, 3, 2) を最後までトレースする
FE平成14年春 午前 問14で実際に提示された並び (4, 1, 3, 2) を、昇順に整列し終わるまで追ってみます。
本番と同じ見え方でパスごとの状態を記録すると、比較回数の合計が式と一致することも同時に確認できます。
📊 選択ソートのトレース表(4, 1, 3, 2 を昇順に整列)
| パス | 探索範囲(未整列部分) | 見つかった最小値 | 交換の有無 | 比較回数 | 操作後の配列 |
|---|---|---|---|---|---|
| 初期 | A[1]〜A[4] | - | - | - | 4, 1, 3, 2 |
| 1 | A[1]〜A[4](4, 1, 3, 2) | 1(A[2]) | あり(4 ⇄ 1) | 3 | 1, 4, 3, 2 |
| 2 | A[2]〜A[4](4, 3, 2) | 2(A[4]) | あり(4 ⇄ 2) | 2 | 1, 2, 3, 4 |
| 3 | A[3]〜A[4](3, 4) | 3(A[3]=先頭自身) | なし | 1 | 1, 2, 3, 4 |
| 合計 | n=4 | - | 2回(≦ n-1=3) | 6回=4×3/2 | 整列完了 |
目を留めたいのは3パス目。
最小値がすでに未整列先頭にあるため交換は起きず、それでも比較は1回きちんと実行されます。「交換は省略できても比較は省略されない」という点が、後述の回数計算の土台になる。
計算量O(n²)と「不安定」になる理由
比較回数 n(n-1)/2 を展開すると (n²-n)/2 となり、最高次の項だけが残って O(n²) に対応します。データがあらかじめ整列済みでも比較回数は減らず、最良・平均・最悪のすべてが同じオーダ。
この扱い方はオーダ記法(計算量)の定義どおりです。
安定性については「不安定」に分類されます。離れた2要素を直接入れ替えるため、同じ値どうしの元の前後関係が保証されないからです。
配列を2つの領域に分けて見ると、この性質の出どころがつかみやすくなります。
📊 選択ソートの2ブロック構成図
境界が左から右へ1つずつ移動していく構造
確定済み。二度と動かない
毎パス全走査される対象
離れた2要素を直接入替え
入替えで崩れる=不安定
挿入ソートは整列済み領域の中身が動くが、選択ソートは入った値が動かない
📝 選択ソートのまとめ
・未整列部分の最小値を探し、未整列先頭と交換する動作の繰り返し
・比較回数は並び順に関係なく常に n(n-1)/2 回
・交換回数は1パス1回以下、全体で最大 n-1 回
・計算量は最良も最悪も O(n²)、安定性は「不安定」
試験ではこう出る!出題パターンとひっかけ対策
出題パターン分析
選択ソートが単独で正解になる問題は、実は型が限られています。
選択ソートの過去問実績一覧を開く(7件)
FE 平成14年春 午前 問13:最大値選択法で大きい順に整列する流れ図の、*印(比較)実行回数を表す式/正解 イ(n(n-1)/2)/選択ソートが主題・正解
FE 平成14年秋 午前 問13:「A[1]〜A[n]の最小要素をA[1]と交換、次にA[2]〜A[n]の最小要素をA[2]と交換…」の比較回数のオーダ/正解 エ(O(n²))/主題・正解
FE 平成23年6月修了 問7:流れ図に従い選択ソートで大きい順に整列するときのα印(比較)実行回数の式/正解 ア(n(n-1)/2)/主題・正解
FE 平成14年春 午前 問14:(4, 1, 3, 2) の入替え過程からアルゴリズム名を特定/正解 ウ(挿入ソート)/選択ソートは誤答選択肢イ
FE 平成30年秋 午前 問6(出題歴:H16秋 問13/H21秋 問6/R8 問2):クイックソートの処理方法の説明を選ぶ/正解 ウ/誤答選択肢イ「データ中の最小値を求め、次にそれを除いた部分の中から最小値を求める」が基本選択法の説明
AP 令和4年秋 午前 問6:流れ図から整列アルゴリズムを特定/正解 エ(バブルソート)/選択ソートは誤答選択肢イ
AP 令和元年秋 午前 問8(出題歴:ソフトウェア開発技術者 H18春 問12):分割統治を利用した整列法はどれか/正解 イ(クイックソート)/選択ソートは誤答選択肢ウ
📝 IPA試験での出題パターン
パターン1:計算量・回数型
比較回数の式やオーダを問う型(FE H14春 問13/FE H14秋 問13/FE H23年6月修了 問7)。選択ソートが正解として問われるのは事実上この型だけ。
パターン2:説明文選択型
4手法の説明文が並ぶ型(FE H30秋 問6系列)。選択ソートは主にクイックソートを問う設問の誤答選択肢として配置される。
パターン3:トレース・流れ図特定型
配列の状態推移や流れ図から手法名を選ぶ型(FE H14春 問14/AP R4秋 問6)。正解はバブル・挿入になる場合が多く、選択ソートは消去法で切る側。
記事の重心はパターン1に置き、パターン2・3は「キーワードで即座に切る」対応で足ります。
筆者も受験時、選択ソートが正解になる問題より、他手法の設問の誤答選択肢として出会う回数のほうが多いと感じました。覚え方を「選択=最小値を探しに行く/挿入=取り出した1つを差し込む」の一文に統一してから、迷いはほぼ消えている。
ひっかけポイントと対策
誤答選択肢には他手法の説明文がそのまま入ります。見分けるキーワードを表で押さえてください。
⚠️ ひっかけ早見表
| 誤答の値・選択肢 | その正体 |
|---|---|
| 隣り合ったデータの比較と入替え | バブルソートの説明 |
| 整列済み列の正しい位置に追加 | 挿入ソートの説明 |
| 基準値で大小2グループに分割 | クイックソート(分割統治) |
| 比較 n-1 回・交換 n(n-1)/2 回 | 比較と交換を逆にした数値ひっかけ |
📝 試験区分別の対策方針
・FE科目A:n(n-1)/2 を即答できる状態まで固める
・FE科目B:擬似言語の二重ループと min 更新条件で練習
・AP:説明文選択型・分割統治型の誤答選択肢に備える
比較回数 n(n-1)/2・交換回数 n-1 を3ステップで導く計算問題の解き方
まず基本3手法を回数の観点で切り分けます。バブルソートとの違いは値の動き方、挿入ソートとの違いは比較回数の安定性に現れる。
📊 3ソートの回数比較マトリクス
| 比較軸 | 選択ソート | バブルソート | 挿入ソート |
|---|---|---|---|
| 比較回数 | 常に n(n-1)/2(並びに依存しない) | 最大 n(n-1)/2 | 最悪 n(n-1)/2・最良 n-1 |
| 交換/移動回数 | 最大 n-1 回(3手法で最小) | 最大 n(n-1)/2 回 | シフトが多数発生 |
| 値の動き方 | 離れた2要素を1回だけ交換 | 隣接2要素を何度も交換 | 大きい要素を右へシフト |
| 1パス後の確定側 | 先頭側 | 末尾側 | 先頭側 |
| 安定性 | 不安定 | 安定 | 安定 |
ここからが本題の解法です。題材はFE平成14年春 午前 問13、最大値選択法の流れ図で*印(比較)の実行回数を表す式を選ぶ問題。式を暗記していなくても、次の3ステップで確実に絞り込めます。
ステップ1:n に小さい具体値を代入する。
n=5 とすれば、1パス目の比較は4回、以降は3回・2回・1回と1つずつ減っていく。
ステップ2:合計を出す。
4+3+2+1=10 となり、これは (n-1) から 1 までの和、つまり n(n-1)/2 の値と一致します。
ステップ3:選択肢に n=5 を代入し、10 になる式を選ぶ。
n(n-1)/2=5×4/2=10 で合致するため、正解はイ。n²/2 や n-1 は値が合わず、その場で切れます。
あわせて押さえたいのが回数の非対称性です。比較は未整列部分を必ず全走査するため常に最大回数、交換は各パスで1回以下。
この差から、比較 n(n-1)/2 に対して交換は最大 n-1 回にとどまります。
比較回数がデータの並びに左右されないのは基本3手法のうち選択ソートだけで、ここが計算問題の出題根拠になっている。
1パス目の見え方が同じで混同しやすい場合は、挿入ソート(基本挿入法)の判別法もあわせて確認してください。
実務でソートを自前実装する場面はほぼなく、DBの ORDER BY や標準ライブラリに任せるのが常識です。
ただし「交換回数が最大 n-1 回」という性質は、レコードそのものの移動コストが高い場面で意味を持ちます。
サイズの大きい構造体の入れ替えや、媒体上でレコードを物理的に動かす処理が典型例。O(n²)の手法を学ぶ価値は、この種のコスト構造を見る目を養う点にある。
【確認テスト】選択ソートの理解度チェック
Q. n 個のデータを選択ソート(基本選択法)で昇順に整列するときの、要素同士の比較回数とデータの交換回数の組合せとして、最も適切なものはどれか。
- A. 比較回数は n-1 回、交換回数は n(n-1)/2 回
- B. 比較回数は n(n-1)/2 回、交換回数は最大 n-1 回
- C. 比較回数も交換回数も、ともに n(n-1)/2 回
正解と解説を見る
正解:B
解説:
比較回数は各パスで (n-1)、(n-2)、…、1 回と減っていき、合計は (n-1)+(n-2)+…+1=n(n-1)/2 回。この値はデータの並び順に関係なく固定です。一方、交換は「未整列部分の最小値を未整列先頭へ移す」ためにパスの最後で1回行われるだけで、最小値がすでに先頭にあれば交換は起こりません。パス数は n-1 なので、交換回数は最大 n-1 回にとどまります。
Aが不正解の理由:比較回数と交換回数を入れ替えた数値ひっかけです。走査のたびに比較が発生するため、比較回数が n-1 回で済むことはありません。
Cが不正解の理由:その正体はバブルソートの最悪ケースです。逆順データでは比較のたびに隣接要素の交換が発生し、両方が n(n-1)/2 回に達します。選択ソートは交換をパスの最後にまとめて1回行うため、この値には一致しません。
選択ソートの関連用語ネットワークと次に学ぶ手法
選択ソートは前提知識も発展先もはっきりしているため、周辺用語とセットで整理すると記憶が安定します。
📊 関連用語マップ
| カテゴリ | 関連用語 |
|---|---|
| 前提知識 | データ構造(配列・リスト)、整列アルゴリズム(ソート)、オーダ記法(計算量) |
| 関連用語 | バブルソート、挿入ソート(基本挿入法)、基本選択法/最大値選択法(同義) |
| 発展 | ヒープソート、クイックソート、シェルソート |