【基本情報技術者試験・科目B】クイックソートを擬似言語で理解する

基本情報技術者試験（科目B）では、

クイックソートを実装できるかよりも、

  • 擬似言語を正しく読めるか
  • 処理の流れを追えるか

が問われます。

この記事では、クイックソートを

「試験中に読めること」に焦点を当てて整理します。

クイックソートとは

クイックソートは、配列を分割しながら並び替える

分割統治法の代表的なアルゴリズムです。

一度の処理で全体を並び替えるのではなく、

  • 基準となる値を1つ決める
  • 配列を左右に分ける
  • 同じ処理を繰り返す

という流れで進みます。

クイックソートの考え方

クイックソートの基本的な考え方は次の通りです。

  1. 配列の中から 基準値（pivot） を選ぶ
  2. pivot より小さい要素を左側に集める
  3. pivot より大きい要素を右側に集める
  4. 左右の配列に対して、同じ処理を繰り返す

重要なのは、

pivot を基準に配列を分けていくという点です。

基本情報試験向け 擬似言語

試験で使われる表記に合わせた、

シンプルな擬似言語例です。

PROCEDURE QuickSort(A)
  IF LENGTH(A) > 1 THEN
    pivot ← A[1]

    L ← pivot より小さい要素の配列
    R ← pivot より大きい要素の配列

    QuickSort(L)
    QuickSort(R)

    A ← L + pivot + R
  ENDIF
ENDPROCEDURE

読み取りのポイント

  • 代入は = ではなく ←
  • 配列の添字は 1 から始まる
  • 再帰呼び出しはL と R に対して行われている

サンプルデータで処理を追う

次の配列を例に、処理の流れを確認します。

A ← [ 5, 2, 4, 1, 3 ]

1回目の処理

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

この時点で、

5 は最終位置が確定しています。

2回目（左側の配列）

[ 2, 4, 1, 3 ]
  • pivot ← 2
  • L ← [ 1 ]
  • R ← [ 4, 3 ]
[ 1 ] + 2 + [ 4, 3 ]

さらに再帰を進めると…

最終的に配列は次のようになります。

[ 1, 2, 3, 4, 5 ]

試験でよくある勘違い

クイックソートは速いアルゴリズム？

理論的には高速ですが、

試験では速度比較はほとんど問われません。

重要なのは処理の流れです。

その場で要素を入れ替える？

試験の擬似言語では、

  • 配列を分割
  • 結合して結果を作る

という 概念的な書き方 が使われます。

pivot は必ず中央値？

試験では、

  • 先頭要素
  • 任意の要素

が pivot として使われることが多く、

中央値である必要はありません。

科目Bでの着眼点

  • 再帰が どこで終了するか
  • どの時点で 値が確定するか
  • 1回の処理では 全体が完成しないこと

特に、

この時点で確定している要素はどれか

という問い方は頻出です。

まとめ

  • クイックソートは基準値で分割し、同じ処理を繰り返すアルゴリズム
  • 実装できなくても問題ありません
  • 擬似言語を読んで、処理を追えることが重要です

基本情報技術者試験では、

「動きを理解しているか」が合否を分けます。

訪問数 3 回, 今日の訪問数 3回

アルゴリズム,基本情報技術者,情報処理試験

Posted by hidepon