初学者のためのソートアルゴリズム完全ガイド

2026年2月3日

― 擬似言語と手書きトレースで理解する「並び替え」 ―

はじめに

ソート（並び替え）は、

基本情報技術者試験・科目Bで最も重要なアルゴリズム分野の一つです。

しかし多くの初学者が、

• コードは読めるが、何をしているかわからない
• 途中で配列がどう変化しているか追えない
• ループが「回っている理由」が見えない

という壁にぶつかります。

この記事では、

• 擬似言語（試験形式）
• 同一の配列データ
• 1回目・2回目の配列状態を手書きで追えるトレース表

を組み合わせて、

「頭の中で動きを再生できる」ことを目的に解説します。

はじめに（この教材の使い方）

この記事で扱うソートアルゴリズムの擬似言語コードは、

以下の 擬似言語シミュレーター を使って 実際に動かすことができます。

▶ 擬似言語実行環境（Pseudo-ide）

この教材のおすすめ学習手順

1. まずコードを読まずに配列だけ見る
2. 次に手書きトレース用プリントで
   • 1回目
   • 2回目の配列状態を自分で書く
3. その後、Pseudo-ide にコードを貼り付けて
   • 実行
   • ステップ実行で 自分の予想と一致するか確認
4. 最後にコードを読む

👉

「コード → 実行」ではなく

「予想 → 実行 → 確認」

これが科目Bで本当に力がつく順番です。

---

共通の前提（必ず確認）

配列と添字

本記事では、基本情報技術者試験の表記に合わせて

配列の添字は 1 から始まるとします。

A ← [ 7, 3, 9, 4, 6 ]

添字	値
A[1]	7
A[2]	3
A[3]	9
A[4]	4
A[5]	6

---

以降、文中のサンプル疑似コードは、上記の擬似言語シミュレーターでは、動作しません
考え方の参考としてください

擬似言語シミュレーター中のサンプルは動作します

1. バブルソート（Bubble Sort）

アルゴリズムの考え方

• 隣り合う要素を比較
• 大きい値が右へ移動
• 外側ループ1回で、末尾が1つ確定

擬似言語

FOR i ← 1 TO N - 1
  FOR j ← 1 TO N - i
    IF A[j] > A[j + 1] THEN
      TEMP ← A[j]
      A[j] ← A[j + 1]
      A[j + 1] ← TEMP
    ENDIF
  ENDFOR
ENDFOR

手書きトレース用（1回目・2回目）

初期状態

[ 7, 3, 9, 4, 6 ]

1回目（i = 1）

比較	配列
7 と 3	3, 7, 9, 4, 6
7 と 9	3, 7, 9, 4, 6
9 と 4	3, 7, 4, 9, 6
9 と 6	3, 7, 4, 6, 9

→ 9 が確定

2回目（i = 2）

比較	配列
3 と 7	3, 7, 4, 6, 9
7 と 4	3, 4, 7, 6, 9
7 と 6	3, 4, 6, 7, 9

---

2. 選択ソート（Selection Sort：昇順）

アルゴリズムの考え方

• 未整列部分から 最小値を探す
• 先頭と入れ替える
• 交換は1回だけ

擬似言語

FOR i ← 1 TO N - 1
  MIN_POS ← i
  FOR j ← i + 1 TO N
    IF A[j] < A[MIN_POS] THEN
      MIN_POS ← j
    ENDIF
  ENDFOR
  IF MIN_POS != i THEN
    SWAP A[i], A[MIN_POS]
  ENDIF
ENDFOR

手書きトレース用

初期状態

[ 7, 3, 9, 4, 6 ]

1回目（i = 1）

• 最小値 → 3（位置2）

[ 3, 7, 9, 4, 6 ]

2回目（i = 2）

• 最小値 → 4（位置4）

[ 3, 4, 9, 7, 6 ]

---

3. 挿入ソート（Insertion Sort）

アルゴリズムの考え方

• 左側は常に整列済み
• 新しい値を「正しい位置」に挿入

擬似言語

FOR i ← 2 TO N
  KEY ← A[i]
  j ← i - 1
  WHILE j >= 1 AND A[j] > KEY
    A[j + 1] ← A[j]
    j ← j - 1
  ENDWHILE
  A[j + 1] ← KEY
ENDFOR

手書きトレース用

初期状態

[ 7, 3, 9, 4, 6 ]

1回目（i = 2, KEY = 3）

[ 3, 7, 9, 4, 6 ]

2回目（i = 3, KEY = 9）

[ 3, 7, 9, 4, 6 ]（変化なし）

---

4. クイックソート（Quick Sort）

アルゴリズムの考え方

• pivot を基準に分割
• 左右を再帰的に処理
• pivot の位置が確定する

手書きトレース（最初の分割）

初期状態（pivot = 6）

[ 7, 3, 9, 4, 6 ]

分割後

[ 3, 4, 6, 7, 9 ]

→ 6 の位置が確定

---

5. マージソート（Merge Sort）

アルゴリズムの考え方

• 分割 → 整列 → マージ
• 安定ソート
• 作業用配列を使用

手書きトレース（マージ部分）

左右に分割後

左:  [ 3, 7, 9 ]
右:  [ 4, 6 ]

マージ結果

[ 3, 4, 6, 7, 9 ]

---

6. 降順ソート（Selection Sort応用）

違いは「比較条件」だけ

IF A[j] > A[MAX_POS] THEN

手書きトレース

初期状態

[ 7, 3, 9, 4, 6 ]

1回目

[ 9, 3, 7, 4, 6 ]

2回目

[ 9, 7, 3, 4, 6 ]