基本情報技術者試験に頻出のソートをサンプルデータで整理する
基本情報技術者試験（特に科目B）では、ソートアルゴリズムについて 名前の暗記 よりも、
- この処理は何をしているのか
- この for 文・while 文で配列はどう変化するのか
を読み取れるかが問われます。
そこで本記事では、最初に共通のサンプルデータを定義し、各ソートがそのデータをどう並び替えるかを確認していきます。
目次
サンプルデータ（全ソート共通）
以降の説明では、次の配列を例として使用します。
A = [ 5, 2, 4, 1, 3 ]この配列を 昇順（小さい順） に並び替えることを考えます。
最終的な正解は次の形です。
[ 1, 2, 3, 4, 5 ]1. バブルソート（Bubble Sort）
考え方
- 隣り合う要素を比較する
- 順番が逆なら入れ替える
- 大きい値が右端に押し出されていく
擬似コード例
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サンプルデータでの動き（イメージ）
初期状態
[ 5, 2, 4, 1, 3 ]1回目の外側ループ後
[ 2, 4, 1, 3, 5 ]👉 最大値 5 が右端に確定
ポイント
- 隣同士を比較して交換
- 動きは単純だが比較回数が多い
2. 選択ソート（Selection Sort）
考え方
- 未整列部分から最小値を探す
- それを先頭と交換する
- 左から順に位置を確定させる
擬似コード例
for i ← 1 to N - 1
min ← i
for j ← i + 1 to N
if A[j] < A[min] then
min ← j
endif
endfor
TEMP ← A[i]
A[i] ← A[min]
A[min] ← TEMP
endforサンプルデータでの動き
初期状態
[ 5, 2, 4, 1, 3 ]1回目（最小値 1 を先頭へ）
[ 1, 2, 4, 5, 3 ]👉 先頭から順に確定していく
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サンプルデータでの動き（途中）
[ 5 | 2, 4, 1, 3 ]
→ [ 2, 5 | 4, 1, 3 ]
→ [ 2, 4, 5 | 1, 3 ]👉 要素をずらしながら挿入
4. クイックソート（Quick Sort）
考え方
- 基準値（ピボット）を1つ選ぶ
- 小さいグループと大きいグループに分割
- 同じ処理を繰り返す
擬似コード例（概念）
if 配列の要素数 > 1 then
pivot を選ぶ
pivotより小さい配列 L
pivotより大きい配列 R
QuickSort(L)
QuickSort(R)
endifサンプルデータでの分割例
pivot = 3
[ 2, 1 ] | 3 | [ 5, 4 ]👉 基準で分ける発想が重要
5. マージソート（Merge Sort）
考え方
- 配列を半分に分ける
- 小さな配列を整列
- 最後にマージする
擬似コード例（概念）
if 配列の要素数 > 1 then
左半分 L
右半分 R
MergeSort(L)
MergeSort(R)
L と R をマージ
endifサンプルデータの流れ
[5, 2, 4, 1, 3]
→ [5, 2] と [4, 1, 3]
→ 整列後に統合まとめ（基本情報向け）
- ソートは 暗記するものではない
- サンプルデータを頭に置き、
- どこが確定するか
- 何を比較しているかを追うことが重要
👉 「この処理を実行した後、配列はどうなるか」
これが基本情報で最もよく問われます。
訪問数 5 回, 今日の訪問数 5回