基本情報技術者試験【アルゴリズム第5回】ソートアルゴリズム完全攻略｜バブル・選択・挿入ソートを図解とトレースで徹底解説【2026年版】

「ソートって種類が多くてどれを覚えればいいかわからない」「途中経過を問われると手が止まる」「何したらええかわからへん」

そう感じている方へ。ソートアルゴリズムは途中経過のパターンを覚えるだけで、試験問題の大半を解けるようになります。

基本3ソートは基本情報でも頻出なので、仕組みとプログラムを必ず理解しておくことを強くおすすめします。 この記事で一気に攻略しましょう。

この記事でわかること

• ソートアルゴリズムとは何か

• バブルソートの仕組み・疑似言語実装・途中経過

• 選択ソートの仕組み・疑似言語実装・途中経過

• 挿入ソートの仕組み・疑似言語実装・途中経過

• クイックソートとマージソートの概念

• 安定ソートと不安定ソートの違い

• 各ソートの計算量と使い分け

• 試験頻出パターンと時間短縮テクニック

1. ソートアルゴリズムとは

定義

ソートとは、複数のデータが並んだ列を、何らかの順序に基いて順番通りになるよう並べ替えること（整列させること）です。数値を大きい順または小さい順に並べたり、文字をアルファベット順や五十音順に並べたり、日時を古い順または新しい順に並べ替えることが該当します。

身近な例

ネットショッピングで「価格が安い順」「評価が高い順」に並び替えるとき、裏側ではソートアルゴリズムが動いています。

試験では「ソート後の途中経過がどうなるか」「何回の比較・交換が必要か」を問われます。動きをイメージできれば確実に解けます。

昇順と降順

昇順は小さい順（1, 2, 3, 4, 5）、降順は大きい順（5, 4, 3, 2, 1）です。試験問題では「昇順に整列せよ」という指定が多いです。

swap（交換）とは

ソートでは2つの要素を入れ替える「swap」操作が頻繁に登場します。一時変数 tmp を使わないと元の値が消えてしまうため、必ず以下のパターンで行います。

tmp  ← a[i]　一時的に退避
a[i] ← a[j]　入れ替え
a[j] ← tmp　 入れ替え

2. バブルソート

バブルソートとは

池の底から表面に泡が浮き上がるように、配列の後ろから前に小さな値が浮かび上がるので、バブル（bubble = 泡）ソートと呼びます。

隣り合う2つの要素を比較し、順序が逆であれば交換する操作を繰り返します。

バブルソートの手順（昇順）

1回の通過（パス）で、最大値が末尾に確定します。

バブルソートのトレース

配列 {6, 4, 2, 8} を昇順にソートする場合：

1パス目：

1パス目終了：{4, 2, 6, 8}（8が確定）

2パス目：

2パス目終了：{2, 4, 6, 8}（6が確定）

3パス目：{2,4,6,8} → そのまま → 完了

最終結果：{2, 4, 6, 8}

バブルソートの疑似言語実装

整数型の配列: a ← {6, 4, 2, 8}
整数型: i, j, tmp
for（i を 1 から aの要素数-1 まで 1 ずつ増やす）
　for（j を 1 から aの要素数-i まで 1 ずつ増やす）
　　if（a[j] > a[j+1]）
　　　tmp    ← a[j]
　　　a[j]   ← a[j+1]
　　　a[j+1] ← tmp
　　endif
　endfor
endfor

バブルソートの特徴

3. 選択ソート

選択ソートとは

選択ソートは、配列の最小値（最大値）を持つ要素を探し、それと先頭の要素と交換することで整列を行うアルゴリズムです。

「未整列部分から最小値を選んで先頭に持ってくる」操作を繰り返します。

選択ソートの手順（昇順）

1回の操作で、先頭から1つずつ確定していきます。

選択ソートの比較回数と交換回数

選択ソートの比較回数は入力状態によらず常に一定で、n(n-1)÷2 回になります。これは未整列部分全体を毎回走査して最小値を探すためです。

交換回数は選択ソートの大きな特徴で、最大でも n-1 回です。1回のパスで最小値を確定させ、その1要素だけを交換するため、交換回数がバブルソートに比べて大幅に少なくなります。交換コスト（データの移動コスト）が高い場面で有効です。

選択ソートのトレース

配列 {6, 4, 2, 8} を昇順にソートする場合：

最終結果：{2, 4, 6, 8}

選択ソートの疑似言語実装

整数型の配列: a ← {6, 4, 2, 8}
整数型: i, j, minIdx, tmp
for（i を 1 から aの要素数-1 まで 1 ずつ増やす）
　minIdx ← i
　for（j を i+1 から aの要素数 まで 1 ずつ増やす）
　　if（a[j] < a[minIdx]）
　　　minIdx ← j
　　endif
　endfor
　tmp        ← a[i]
　a[i]       ← a[minIdx]
　a[minIdx]  ← tmp
endfor

選択ソートの特徴

4. 挿入ソート

挿入ソートとは

単純挿入ソートとは、「着目要素をそれより先頭側の適切な位置に"挿入する"作業を繰り返してソートする」整列アルゴリズムのことです。

トランプの手札を整理するときに、1枚ずつ適切な位置に差し込んでいく操作をイメージしてください。

挿入ソートの手順（昇順）

挿入ソートのトレース

配列 {6, 4, 2, 8} を昇順にソートする場合：

最終結果：{2, 4, 6, 8}

挿入ソートの疑似言語実装

整数型の配列: a ← {6, 4, 2, 8}
整数型: i, j, tmp
for（i を 2 から aの要素数 まで 1 ずつ増やす）
　tmp ← a[i]
　j   ← i - 1
　while（j ≧ 1 and a[j] > tmp）
　　a[j+1] ← a[j]
　　j       ← j - 1
　endwhile
　a[j+1] ← tmp
endfor

挿入ソートの特徴

挿入ソートは、バブルソートや選択ソートに比べてデータが昇順に近ければ近いほど比較・交換回数が減少するため、他の単純ソートよりも速度が速いです。

5. クイックソートとマージソートの概念

クイックソート

クイックソートとは、基準値を決めて、それより大きい数字のグループと小さい数字のグループに分ける操作を繰り返して昇順に整列させるアルゴリズムです。

基準値（ピボット）を選び、ピボットより小さい値を左、大きい値を右に振り分けます。この操作を再帰的に繰り返します。

マージソート

配列を2つに分割し、それぞれをソートしてから結合（マージ）する方法です。分割 → ソート → 結合を再帰的に繰り返します。

6. 安定ソートと不安定ソートの違い

安定ソートとは

同じ値が2つ以上あるときにソートしても同じ値の順番が変わらない（保存される）ソートのことを安定ソートと呼びます。安定ソートであれば「80点の田中さん」と「80点の佐藤さん」の順序は必ず元のデータと同じになります。一方、安定でないソート（不安定ソート）の場合、同じ値の「80点の田中さん」と「80点の佐藤さん」の順序が入れ替わってしまうことがあります。

各ソートの安定性まとめ

試験では「このソートは安定か不安定か」という問いが出ます。安定ソートの代表はバブル・挿入・マージ、不安定ソートの代表は選択・クイックと覚えましょう。

7. 各ソートの計算量と使い分け

試験での見極め方

問題文に「隣り合う要素を比較・交換」→ バブルソート、「最小値を選んで先頭と交換」→ 選択ソート、「適切な位置に挿入」→ 挿入ソート、「基準値で2グループに分割」→ クイックソート、「分割して結合」→ マージソートです。

8. 試験頻出パターンと時間短縮テクニック

パターン①：n回のパス後の途中経過を答える

バブルソートで最頻出の問題です。「3パス後の配列はどうなるか」という形式です。

パスごとにトレース表を書いて1ステップずつ確認します。焦って暗算するとミスします。

パターン②：比較回数・交換回数を答える

n個の要素に対して基本3ソートの比較回数はすべて n(n-1)÷2 回です。n = 5 なら 5×4÷2 = 10回です。

交換回数は問題によって異なります。実際にトレースして数えるのが確実です。

パターン③：どのソートかを当てる

途中経過の配列が与えられて「これは何ソートか」を答える問題です。各ソートの特徴的な動きを覚えておきましょう。

バブルソートは末尾から確定する、選択ソートは先頭から確定する、挿入ソートは先頭部分が常に整列済みになっているという特徴があります。

テクニック①：トレース表は必ず書く

ソート問題はトレース表を書かずに頭の中で解こうとするとミスします。試験本番でもメモ用紙にトレース表を書く習慣をつけましょう。

テクニック②：確定した要素を目印にする

バブルソートは右端から確定、選択ソートは左端から確定していきます。「どこまで確定したか」を意識しながらトレースすると間違いが減ります。

テクニック③：swapの順番に注意する

まとめ

ソートアルゴリズムは次回の再帰・木構造・グラフの理解にもつながります。特にクイックソートは再帰的な発想が基本になるため、第6回でより深く解説します。

関連記事

• 【アルゴリズム第1回】流れ図と基本3構造

• 【アルゴリズム第2回】疑似言語の読み方完全攻略

• 【アルゴリズム第3回】配列・スタック・キューを完全理解

• 【アルゴリズム第4回】探索アルゴリズム完全攻略

• 【アルゴリズム第6回】再帰・木構造・グラフ（近日公開）

• IPA公式：基本情報技術者試験 https://www.ipa.go.jp/shiken/kubun/fe.html