アルゴリズム
ソートアルゴリズムの種類と比較【基本情報技術者試験 科目B対策】
公開日: 2026年5月6日
基本情報技術者試験の科目B（アルゴリズムとプログラミング）では、ソートアルゴリズムの処理の流れや計算量を問う問題が頻出です。
この記事では、主要な4つのソートアルゴリズム（バブルソート・選択ソート・挿入ソート・クイックソート）の仕組みと特徴を、配列の動きを追いながら解説します。
バブルソート
隣り合う要素を比較・交換しながら、最大値を順に末尾へ「泡（バブル）」のように浮き上がらせるソートです。
処理の流れ（配列：5, 3, 4, 1, 2）
5 3 4 1 2
→
3 4 1 2 5
→
3 1 2 4 5
→
1 2 3 4 5
for i = 0 to n-2:
for j = 0 to n-2-i:
if A[j] > A[j+1]:
A[j] と A[j+1] を交換
計算量：O(n²) 特徴：実装は単純だが効率は悪い。
選択ソート
未整列部分から最小値を選んで先頭と交換することを繰り返します。
処理の流れ（配列：5, 3, 4, 1, 2）
5 3 4 1 2
→
1 3 4 5 2
→
1 2 4 5 3
→
1 2 3 5 4
for i = 0 to n-2:
min_idx = i
for j = i+1 to n-1:
if A[j] < A[min_idx]:
min_idx = j
A[i] と A[min_idx] を交換
計算量：O(n²) 特徴：交換回数が少ない（最大n-1回）。
挿入ソート
未整列の要素を整列済み部分の適切な位置に「挿入」していくソートです。データがほぼ整列済みの場合に効率的。
処理の流れ（配列：5, 3, 4, 1, 2）
5 | 3 4 1 2
→
3 5 | 4 1 2
→
3 4 5 | 1 2
→
1 3 4 5 | 2
for i = 1 to n-1:
tmp = A[i]
j = i - 1
while j >= 0 and A[j] > tmp:
A[j+1] = A[j]
j = j - 1
A[j+1] = tmp
計算量：O(n²)（最悪）／ O(n)（最良・既にほぼ整列済みの場合）
クイックソート
基準値（ピボット）を選び、それより小さい要素・大きい要素に分割して再帰的にソートします。平均的に最も高速。
procedure quicksort(A, low, high):
if low < high:
pivot = partition(A, low, high) // ピボットの位置を決める
quicksort(A, low, pivot - 1)
quicksort(A, pivot + 1, high)
計算量：平均 O(n log n)、最悪 O(n²)（ピボット選択が偏ったとき）
4つのソートアルゴリズム比較表
| 種類 | 平均計算量 | 最悪計算量 | 特徴 |
|---|
| バブルソート | O(n²) | O(n²) | 実装が最も簡単 |
| 選択ソート | O(n²) | O(n²) | 交換回数が少ない |
| 挿入ソート | O(n²) | O(n²) | ほぼ整列済みデータに強い |
| クイックソート | O(n log n) | O(n²) | 実用的に最速。再帰を使う |
計算量の目安：O(n²) はデータが2倍になると処理時間が約4倍。O(n log n) はデータが2倍になっても処理時間は約2倍強にしかならない。
科目B疑似言語での出題パターン
科目Bでは、ソートのコードを疑似言語で示し「何回目のループで配列がどうなるか」を問う問題が頻出です。
- ループの各回で配列の状態をトレースする練習をする
- 変数の値がどう変化するかをステップごとに追う
- バブルソートの「i回目の外側ループ後に、末尾i個が確定する」という性質を覚える
試験対策まとめ
- バブル・選択・挿入：計算量はすべて O(n²)
- クイックソート：平均 O(n log n)、再帰を使う
- 疑似言語問題はトレース（手でステップを追う）が最強の対策
- Blocklyラボで視覚的にアルゴリズムを確認するのも効果的
← 記事一覧に戻る