基本情報技術者試験に頻出のソートをサンプルデータで整理する

クイックソートを具体化して書きますね。

ポイントは

• 「LENGTH」
• 配列の添字（1始まり）
• 再帰
• 配列の結合

です。

① 基本情報でよく使われる前提（擬似言語の約束）

• 配列の添字：1 から始まる
• LENGTH(A)：配列 A の要素数
• ←：代入
• []：配列
• APPEND(X, v)：配列 X の末尾に v を追加
• +：配列の結合

② クイックソートの疑似コード（関数形式）

クイックソート本体

FUNCTION QuickSort(A)
  N ← LENGTH(A)

  IF N ≤ 1 THEN
    RETURN A
  ENDIF

  pivot ← A[1]

  L ← []   // pivot より小さい要素
  R ← []   // pivot より大きい要素

  FOR i ← 2 TO N
    IF A[i] < pivot THEN
      APPEND(L, A[i])
    ELSE
      APPEND(R, A[i])
    ENDIF
  ENDFOR

  L ← QuickSort(L)
  R ← QuickSort(R)

  RETURN L + [pivot] + R
ENDFUNCTION

👉 試験で非常に典型的な形です。

③ 与えられた配列での実行例

A ← [ 5, 2, 4, 1, 3 ]
A ← QuickSort(A)

処理の流れ（概念）

1回目

• pivot = 5
• L = [2, 4, 1, 3]
• R = []

2回目（L に対して）

• pivot = 2
• L = [1]
• R = [4, 3]

3回目（R に対して）

• pivot = 4
• L = [3]
• R = []

最終結果

[1, 2, 3, 4, 5]

④ 出力（質問にあった print）

print A[1]
print A[2]
print A[3]
print A[4]
print A[5]

出力結果：

1
2
3
4
5

⑤ 試験対策としての重要ポイント

✔ pivot は 先頭要素として書かれることが多い

✔ in-place（交換型）より 配列分割型が試験向き

✔ LENGTH は 普通に使ってOK

✔ 再帰終了条件は N ≤ 1

⑥ よくある出題パターン

• 「この疑似コードの処理回数は？」
• 「pivot が常に最大だった場合の計算量は？」
• 「L と R の中身を問う問題」
• 「再帰呼び出しの回数」

マージソートの疑似コードを、クイックソートと同じ粒度で整理します。

① 擬似言語の前提（前回と同じ）

• 添字は 1 始まり
• LENGTH(A)：配列の要素数
• ←：代入
• []：配列
• APPEND(X, v)：末尾追加

② マージソート全体の疑似コード

MergeSort（分割する側）

FUNCTION MergeSort(A)
  N ← LENGTH(A)

  IF N ≤ 1 THEN
    RETURN A
  ENDIF

  mid ← N DIV 2

  L ← A[1] ～ A[mid]
  R ← A[mid + 1] ～ A[N]

  L ← MergeSort(L)
  R ← MergeSort(R)

  RETURN Merge(L, R)
ENDFUNCTION

③ マージ処理の疑似コード（ここが超重要）

FUNCTION Merge(L, R)
  i ← 1
  j ← 1
  M ← []

  WHILE i ≤ LENGTH(L) AND j ≤ LENGTH(R)
    IF L[i] ≤ R[j] THEN
      APPEND(M, L[i])
      i ← i + 1
    ELSE
      APPEND(M, R[j])
      j ← j + 1
    ENDIF
  ENDWHILE

  WHILE i ≤ LENGTH(L)
    APPEND(M, L[i])
    i ← i + 1
  ENDWHILE

  WHILE j ≤ LENGTH(R)
    APPEND(M, R[j])
    j ← j + 1
  ENDWHILE

  RETURN M
ENDFUNCTION

👉 試験で問われるのは、ほぼこの Merge の中身です。

④ 例：配列での実行

A ← [ 5, 2, 4, 1, 3 ]
A ← MergeSort(A)

分割の流れ

[5, 2, 4, 1, 3]
 → [5, 2] と [4, 1, 3]

[5, 2] → [5] と [2]
[4, 1, 3] → [4] と [1, 3]

マージの流れ

[5] + [2] → [2, 5]
[1] + [3] → [1, 3]
[4] + [1, 3] → [1, 3, 4]
[2, 5] + [1, 3, 4] → [1, 2, 3, 4, 5]

⑤ 出力例（print）

print A[1]
print A[2]
print A[3]
print A[4]
print A[5]

出力：

1
2
3
4
5

⑥ クイックソートとの比較（試験超重要）

⑦ 試験での頻出ポイント

✔ mid ← N DIV 2

✔ Merge の while 条件

✔ 片方が先に尽きた後の 残り要素処理

✔ 計算量は 常に O(N log N)