2026年5月2日
情報Ⅰのテストで「この配列をバブルソートで並べ替えたとき、3回目の比較後の状態を答えよ」と出題されて、頭が真っ白になった経験はありませんか？
アルゴリズムやソートは、仕組みを理解せずに暗記しようとすると混乱します。でも、実際に数字を動かしながら手順を追えば、意外とシンプルです。
この記事では、バブルソート・選択ソート・挿入ソートの3つを、具体的な数列を使ってステップごとに解説します。テストのトレース問題も自信を持って解けるようになりましょう。
情報Ⅰの学習全体の進め方は「情報Ⅰの準備と勉強法」でまとめています。
アルゴリズムとは？
アルゴリズムとは、問題を解くための手順を明確に示したものです。
日常生活の例で考えてみましょう。カレーを作るレシピは、アルゴリズムの一種です。
- 野菜を切る
- 肉を炒める
- 野菜を加えて炒める
- 水を入れて煮る
- ルーを入れて混ぜる
このように「誰がやっても同じ結果になる手順」がアルゴリズムです。
コンピュータのアルゴリズムも同じ考え方です。コンピュータは自分で考えることができません。人間が「この順番でこう処理しなさい」と正確に指示する必要があります。
なぜアルゴリズムを学ぶのか
同じ問題でも、手順の違いで処理速度が大きく変わります。たとえば100万件のデータを並べ替えるとき、良いアルゴリズムなら数秒で終わりますが、悪いアルゴリズムだと何時間もかかることがあります。
情報Ⅰでは、アルゴリズムの基本としてソート（並べ替え）と探索（検索）を学びます。プログラミングとの関係は「情報Ⅰプログラミング入門」で詳しく解説しています。
フローチャートの読み方
フローチャートとは、アルゴリズムの手順を図で表したものです。テストではフローチャートの穴埋め問題がよく出ます。
基本記号
- 端子（角丸の四角）: 開始と終了を表す
- 処理（四角）: 計算や代入を表す
- 判断（ひし形）: 条件分岐を表す。Yes/Noで分かれる
- ループ（六角形や矢印の繰り返し）: 繰り返し処理を表す
- 矢印: 処理の流れを表す
簡単な例：2つの数の大きい方を表示する
- 開始
- AとBを入力する
- A > B か？ → Yesなら「Aを表示」、Noなら「Bを表示」
- 終了
テストでのコツ: フローチャートを読むときは、具体的な数値を入れて手順を追いましょう。A=5, B=3のように値を決めて、矢印に沿って進めると理解しやすくなります。
フローチャートの詳しい書き方は「情報Ⅰフローチャートの書き方」で学べます。
バブルソート
バブルソート（隣接交換法）は、隣り合う2つの要素を比較して、順番が逆なら交換する方法です。泡（バブル）が水面に浮かび上がるように、大きい値が端に移動していきます。
仕組み
- 配列の先頭から隣り合う2つを比較する
- 左が右より大きければ交換する
- 配列の最後まで繰り返す（1回のパス）
- パスを繰り返し、交換が起きなくなったら終了
具体例：[5, 3, 8, 1, 4] を昇順に並べ替える
1回目のパス:
[5, 3, 8, 1, 4] → 5と3を比較 → 交換 → [3, 5, 8, 1, 4]
[3, 5, 8, 1, 4] → 5と8を比較 → そのまま → [3, 5, 8, 1, 4]
[3, 5, 8, 1, 4] → 8と1を比較 → 交換 → [3, 5, 1, 8, 4]
[3, 5, 1, 8, 4] → 8と4を比較 → 交換 → [3, 5, 1, 4, 8]
1回目のパス終了: [3, 5, 1, 4, 8] ← 8が確定
2回目のパス:
[3, 5, 1, 4, 8] → 3と5を比較 → そのまま
[3, 5, 1, 4, 8] → 5と1を比較 → 交換 → [3, 1, 5, 4, 8]
[3, 1, 5, 4, 8] → 5と4を比較 → 交換 → [3, 1, 4, 5, 8]
2回目のパス終了: [3, 1, 4, 5, 8] ← 5が確定
3回目のパス:
[3, 1, 4, 5, 8] → 3と1を比較 → 交換 → [1, 3, 4, 5, 8]
[1, 3, 4, 5, 8] → 3と4を比較 → そのまま
3回目のパス終了: [1, 3, 4, 5, 8] ← 4が確定
4回目のパス:
[1, 3, 4, 5, 8] → 1と3を比較 → そのまま → 交換なし
交換が起きなかったので終了。結果: [1, 3, 4, 5, 8]
特徴
- 計算量: O(n²)（データ数の2乗に比例して遅くなる）
- 安定ソート: 同じ値の順番が保たれる
- わかりやすさ: 最もシンプルで理解しやすい
選択ソート
選択ソート（直接選択法）は、未整列部分から最小値を見つけて、先頭と交換する方法です。
仕組み
- 配列全体から最小値を見つける
- 最小値を配列の先頭と交換する
- 先頭を除いた残りの部分で同じことを繰り返す
具体例：[5, 3, 8, 1, 4] を昇順に並べ替える
1回目: 全体 [5, 3, 8, 1, 4] から最小値 → 1（4番目）
先頭の5と交換 → [1, 3, 8, 5, 4] 確定: [1 | 3, 8, 5, 4]
2回目: 残り [3, 8, 5, 4] から最小値 → 3（1番目）
すでに先頭なので交換なし 確定: [1, 3 | 8, 5, 4]
3回目: 残り [8, 5, 4] から最小値 → 4（3番目）
先頭の8と交換 → [1, 3, 4, 5, 8] 確定: [1, 3, 4 | 5, 8]
4回目: 残り [5, 8] から最小値 → 5（1番目）
すでに先頭なので交換なし 確定: [1, 3, 4, 5 | 8]
結果: [1, 3, 4, 5, 8]
特徴
- 計算量: O(n²)
- 不安定ソート: 同じ値の順番が変わることがある
- 交換回数が少ない: 各パスで最大1回の交換
配列の操作をプログラムで書く方法は「JavaScriptの配列入門」で学べます。
挿入ソート
挿入ソート（直接挿入法）は、未整列の要素を1つずつ取り出し、整列済み部分の正しい位置に挿入する方法です。トランプの手札を並べ替えるイメージです。
仕組み
- 2番目の要素を取り出す
- 整列済み部分（左側）と比較して、正しい位置に挿入する
- 3番目、4番目…と順に繰り返す
具体例：[5, 3, 8, 1, 4] を昇順に並べ替える
初期状態: 整列済み [5] | 未整列 [3, 8, 1, 4]
1回目: 3を取り出す
整列済み [5] と比較 → 3 < 5 なので5の前に挿入
結果: [3, 5 | 8, 1, 4]
2回目: 8を取り出す
整列済み [3, 5] と比較 → 8 > 5 なのでそのまま末尾
結果: [3, 5, 8 | 1, 4]
3回目: 1を取り出す
整列済み [3, 5, 8] と比較 → 1 < 3 なので先頭に挿入
結果: [1, 3, 5, 8 | 4]
4回目: 4を取り出す
整列済み [1, 3, 5, 8] と比較 → 4 > 3 かつ 4 < 5 なので3と5の間に挿入
結果: [1, 3, 4, 5, 8]
結果: [1, 3, 4, 5, 8]
特徴
- 計算量: O(n²)（最悪の場合）
- 安定ソート: 同じ値の順番が保たれる
- ほぼ整列済みのデータに強い: すでに並んでいる部分が多いと速い
繰り返し処理の書き方は「JavaScriptのループ処理入門」で詳しく学べます。
3つのソートの比較
3つのソートの特徴を表で比較します。
| 項目 | バブルソート | 選択ソート | 挿入ソート |
|---|---|---|---|
| 計算量（最悪） | O(n²) | O(n²) | O(n²) |
| 計算量（最良） | O(n) | O(n²) | O(n) |
| 安定性 | 安定 | 不安定 | 安定 |
| 交換回数 | 多い | 少ない | 中程度 |
計算量O(n²)とは
O(n²)は「データ数nの2乗に比例する」という意味です。データが10個なら約100回、100個なら約10,000回の比較が必要です。データが増えると急激に遅くなります。
安定ソートとは
安定ソートとは、同じ値の要素の順番が並べ替え後も変わらないことです。
例: [3a, 1, 3b, 2] を昇順に並べ替えたとき
- 安定: [1, 2, 3a, 3b]（3aが3bより前のまま）
- 不安定: [1, 2, 3b, 3a]（順番が変わる可能性あり）
テストでは「安定なソートはどれか」と問われることがあります。バブルソートと挿入ソートが安定、選択ソートが不安定と覚えましょう。
使い分け
- データが少ない場合: どれでも大差ない
- ほぼ整列済みのデータ: 挿入ソートが速い
- 交換コストが高い場合: 選択ソート（交換回数が少ない）
テスト頻出問題パターン
パターン1: トレース問題
問題例: 配列 [4, 2, 7, 1] にバブルソートを適用する。1回目のパス終了後の配列を答えよ。
4と2を比較 → 交換 → [2, 4, 7, 1]
4と7を比較 → そのまま → [2, 4, 7, 1]
7と1を比較 → 交換 → [2, 4, 1, 7]
答え: [2, 4, 1, 7]
コツ: 1ステップずつ配列の状態を書き出しましょう。頭の中だけで追うとミスします。
パターン2: 比較回数・交換回数を問う問題
問題例: 要素数5の配列にバブルソートを適用する。最悪の場合の比較回数は何回か。
1回目のパス: 4回比較
2回目のパス: 3回比較
3回目のパス: 2回比較
4回目のパス: 1回比較
合計: 4+3+2+1 = 10回
一般式: n(n-1)/2 回（nはデータ数）
答え: 10回
パターン3: フローチャートの穴埋め
問題例: バブルソートのフローチャートで、「もし A[j] > A[j+1] ならば」の次の処理は何か。
答え: A[j]とA[j+1]を交換する
コツ: フローチャートの穴埋めは、具体的な数値を入れてシミュレーションすると正解が見えます。
パターン4: ソートの種類を判別する問題
問題例: 「未整列部分から最小値を見つけ、先頭と交換する」アルゴリズムの名前を答えよ。
答え: 選択ソート
コツ: 各ソートのキーワードを覚えましょう。
- バブルソート → 「隣り合う要素を比較・交換」
- 選択ソート → 「最小値を見つけて先頭と交換」
- 挿入ソート → 「正しい位置に挿入」
パターン5: 安定性の問題
問題例: 次のソートのうち、安定なソートをすべて選べ。（バブルソート、選択ソート、挿入ソート）
答え: バブルソート、挿入ソート
まとめ
- ✅ アルゴリズムは「問題を解くための明確な手順」
- ✅ バブルソートは隣り合う要素を比較・交換する
- ✅ 選択ソートは最小値を見つけて先頭と交換する
- ✅ 挿入ソートは正しい位置に挿入する
- ✅ 3つとも最悪計算量はO(n²)
- ✅ 安定ソートはバブルと挿入、不安定は選択
- ✅ トレース問題は1ステップずつ書き出して解く
ソートの仕組みは、具体的な数列で手を動かして練習するのが一番の近道です。この記事の例を自分でノートに書いて追ってみてください。
🚀 情報Ⅰの学習をさらに進めよう！
アルゴリズムの考え方は、実際にプログラムを書くときの土台になります。このサイトでは、情報Ⅰに対応した学習コンテンツを無料で提供しています。
情報Ⅰの準備と勉強法を見る →