最終更新日:2026年10月29日
fe fe-technology algorithm sorting
まず結論
基本情報技術者試験でソートアルゴリズムを見分けるときは、「何を基準に、どのように並べ替えるか」を見ます。
まずは次の6つを押さえると、多くの選択肢を切れます。
隣同士を比較して交換
→ バブルソート
一定間隔で取り出した部分列を整列
→ シェルソート
最小値を探して前へ移す
→ 選択ソート
整列済み部分の正しい位置へ入れる
→ 挿入ソート
基準値(ピボット)で小さい側・大きい側に分ける
→ クイックソート
順序木を作り、最大値・最小値を取り出す
→ ヒープソート
特にクイックソートは、基準値を選んで分割するという表現が決め手です。
直感的な説明
数字が書かれたカードを小さい順に並べる場面を考えます。
同じ「並べ替え」でも、やり方はそれぞれ違います。
| 方法 | 直感的なイメージ |
|---|---|
| バブルソート | 隣のカードと比べながら、順番が逆なら交換する |
| シェルソート | 離れた位置のカードを一定間隔でグループ化して先に整える |
| 選択ソート | 残っているカードから最小のものを探して前へ置く |
| 挿入ソート | 既に並んでいる部分の正しい位置へカードを差し込む |
| クイックソート | 基準のカードを決め、小さい組と大きい組に分ける |
| ヒープソート | 順序木を作り、最大値・最小値を順に取り出す |
試験ではアルゴリズム名そのものより、説明文に出てくる動作を拾うのがコツです。
定義・仕組み
バブルソート
隣り合う二つの要素を比較し、順序が逆なら交換します。これを繰り返すことで、大きい値や小さい値が端へ少しずつ移動します。
判断キーワードは、「隣り合う」「比較」「交換」です。
バブルソートは1周ごとに何が確定する?
左から右へ隣り合う値を比較する昇順の例を考えます。
開始 [5, 2, 4, 1]
5と2を交換 [2, 5, 4, 1]
5と4を交換 [2, 4, 5, 1]
5と1を交換 [2, 4, 1, 5] ← 最大値5が右端に確定
次の周回 [2, 4, 1, 5]
4と1を交換 [2, 1, 4, 5] ← 4も確定
次の周回 [1, 2, 4, 5] ← 整列完了
この方式では、1周終わるたびに未整列部分の最大値が右端へ確定します。次の周回では確定した末尾を比較対象から外せます。
ただし、実装によって比較方向が逆なら、小さい値が左端へ確定する場合もあります。試験では「隣り合う要素を比較・交換する」という動作を優先して判断します。
シェルソート
シェルソートは、要素を一定間隔おきに取り出して部分列を作り、それぞれを整列します。
その後、間隔を少しずつ狭めて同じ操作を繰り返し、最後は間隔を1にして整列させます。
判断キーワードは、「一定間隔」「部分列」「間隔を狭める」です。
一定間隔で取り出す
↓
部分列ごとに整列
↓
間隔を狭める
↓
最後は間隔1
選択ソート
未整列部分から最小値(または最大値)を探し、先頭の要素と交換します。
判断キーワードは、「最小値を探す」「未整列部分から選ぶ」です。
挿入ソート
整列済み部分に新しい要素を一つずつ取り込み、正しい位置へ挿入します。
判断キーワードは、「整列済み部分」「正しい位置へ挿入」です。
クイックソート
基準値(ピボット)を一つ選び、データを基準値より小さい側と大きい側に分割します。分割した各グループでも同じ処理を繰り返します。
基準値を選ぶ
↓
小さい側 / 大きい側に分ける
↓
それぞれのグループでも同じ処理を行う
この「分割して、さらに同じ処理を繰り返す」という考え方は、再帰処理とは?呼び出しと戻りを追う方法にもつながります。
ヒープソート
ヒープソートは、要素をヒープ(順序木)に並べ、最大値または最小値を取り出して整列済み部分へ移す操作を繰り返します。
判断キーワードは、「順序木」「ヒープ」「最大値・最小値を取り出す」です。
順序木を作る
↓
最大値・最小値を取り出す
↓
整列済み部分へ移す
↓
残りで繰り返す
探索アルゴリズムとの違いを確認したい場合は、ブロック探索とは?平均比較回数を公式なしで求める方法も参考になります。
基本情報技術者試験の出題範囲は、IPA:試験要綱・シラバスについて で確認できます。
途中経過で見分ける:4種類のソートを動かす
同じ配列 [4, 1, 3, 2] でも、ソートの方式によって途中経過はどう変わるでしょうか?
- ソートの方式を選ぶ。
- 次にどの値が動くか、状態を予想する。
- 「次へ」で進め、ほかの方式と比べる。
見るポイント:並びが同じでも、処理の目的は異なります。
- 挿入ソート:左の整列済み部分へ値を差し込む。
- バブルソート:隣同士を交換し、右端を確定していく。
挿入ソートとバブルソートでは、途中の並びが同じになる場合があります。そのときも値の動かし方を比較しましょう。
この教材の表示範囲: 各方式の代表的な処理単位を1歩ずつ表示します。比較・交換の全命令を再現するものではありません。
選択:未整列部分から最小値を探す
初期状態
オレンジの枠:直前のステップで値が変わった位置。緑:挿入ソートでは「その時点で整列済みの前方部分」、他の方式では「最終位置が確定した部分」です。
次に、どの値が動くでしょうか?
見るポイント:挿入ソートで緑になった [1, 4] の4も、次の挿入で右へ動きます。「整列済み」と「最終位置が確定」は区別しましょう。選択・バブルソートの緑は最終位置が確定した部分です。このクイックソート図では、完了時に全体を緑にします。オレンジ枠は値が変わった位置であり、比較したすべての位置ではありません。
途中の並びだけで断定できる?
選択ソートなら [4,1,3,2] → [1,4,3,2] → [1,2,3,4] となります。一方、挿入ソートも [4,1,3,2] → [1,4,3,2] → [1,3,4,2] → [1,2,3,4] と進みます。
途中状態を省略している場合、同じ二つの状態だけから方式を一意に特定できないことがあります。 設問が「各交換をすべて記録した」のか、「各回の結果だけ示した」のかを確認してください。
科目Aでどう出る?
科目Aでは、アルゴリズムの処理方法を文章で示し、該当する名称を選ばせる問題が典型です。
まず「最初の動作」を見る
長い説明文を最初から最後まで細かく追うより、どのような動作から始まっているかを見ると切り分けやすくなります。
隣り合うデータを比較する
→ バブルソート
一定間隔で部分列を作る
→ シェルソート
未整列部分から最小値を探す
→ 選択ソート
整列済み部分へ新しい値を入れる
→ 挿入ソート
基準値を選んで二つに分ける
→ クイックソート
順序木から最大値・最小値を取り出す
→ ヒープソート
「交換する」「繰り返す」という言葉だけでは判断できません。どのソートでも、交換や繰り返しが現れることがあります。
何を比較するのか、何を探すのか、何を基準に分けるのかまで見るのがポイントです。
| 問題文の手掛かり | 判断 |
|---|---|
| 隣り合うデータを比較・交換 | バブルソート |
| 一定間隔で取り出した部分列を整列 | シェルソート |
| 最小値・最大値を探す | 選択ソート |
| 整列済み部分の適切な位置に追加 | 挿入ソート |
| 基準値・ピボットで二つに分割 | クイックソート |
| 順序木から最大値・最小値を取り出す | ヒープソート |
特にクイックソートでは、「基準値を選ぶ → 小さい側と大きい側に分ける → 分けたグループで同じ処理を行う」という流れが強い判断材料になります。
科目Bではどうつながる?
科目Bでは、ソートの名前を選ぶだけでなく、疑似言語を見て配列の値がどう変わるかを追う問題につながります。
そのときも、まずは次のように処理の種類を見抜きます。
隣接要素を順番に比較している
→ バブルソートの可能性が高い
一定間隔ごとに要素を取り出している
→ シェルソートの可能性が高い
未整列部分から最小値の位置を探している
→ 選択ソートの可能性が高い
前方の整列済み部分へ値を差し込んでいる
→ 挿入ソートの可能性が高い
基準値との大小で範囲を分けている
→ クイックソートの可能性が高い
木構造を使って最大値・最小値を取り出している
→ ヒープソートの可能性が高い
アルゴリズム名が分かると、「次にどの値が動きそうか」を予想しやすくなり、トレースもしやすくなります。
どんな場面で使う?
ソートは、データを一定の順序に並べ、その後の検索や集計をしやすくするときに使います。
例えば、
- 数値を小さい順に並べる
- 名前を五十音順に並べる
- 日付を古い順・新しい順に並べる
といった処理です。
FEでは、実務でどのアルゴリズムを採用するかよりも、処理手順を見てアルゴリズム名を判定する力がまず重要です。
よくある誤解・混同
「交換する」と書いてあればバブルソート
選択ソートでも要素の交換は行います。
バブルソートの決め手は、隣り合う要素を比較することです。
「最小値を前へ移す」と「正しい位置へ挿入する」を混同する
残り全体から最小値を探す
→ 選択ソート
一つの値を整列済み部分へ差し込む
→ 挿入ソート
と切り分けます。
一定間隔で分けるのはクイックソート?
違います。
一定間隔で取り出して部分列を整列
→ シェルソート
基準値で大小に分ける
→ クイックソート
どちらも「分ける」処理がありますが、間隔で分けるか、値の大小で分けるかが違います。
順序木から最小値を取り出すのは選択ソート?
違います。
未整列部分を直接調べて最小値を探す
→ 選択ソート
順序木・ヒープを使って最小値や最大値を取り出す
→ ヒープソート
「最小値を取り出す」という結果だけで決めず、木構造を使っているかを確認します。
「繰り返す」と書いてあればクイックソート
クイックソート以外のソートも処理を繰り返します。
クイックソートの決め手は、基準値(ピボット)を選び、小さい側と大きい側へ分割することです。
クイックソートは「高速なソート」という説明だけで選ぶ
名前に「クイック」とありますが、試験での決め手は速さではありません。
基準値(ピボット)を選び、データを二つのグループに分割することが本質です。
基準値そのものが最終的な中央の値だと思う
ピボットは、データを分割するための基準として選ぶ値です。必ず中央値を選ぶという意味ではありません。
まとめ(試験直前用)
- 隣同士を比較・交換 → バブルソート
- 一定間隔の部分列を整列 → シェルソート
- 最小値を探して前へ → 選択ソート
- 整列済み部分の正しい位置へ入れる → 挿入ソート
- 基準値(ピボット)で小さい側・大きい側に分割 → クイックソート
- 順序木から最大値・最小値を取り出す → ヒープソート
- 「交換」「繰り返す」だけでは決めず、最初に何をしているか・何を使って分けるかを見る
- 科目Bでは、この判断を使って次にどの値が動くかを予想する