データの置き方で速さが変わる — 配列・探索・整列と擬似言語のトレース
IPA擬似言語の記述形式の読み方、トレース表による手動実行、配列・スタック・キュー、線形探索と二分探索、整列アルゴリズムの計算量を学ぶ。
更新日 執筆: PassDojo 編集部
目次読了目安 約9分
科目Bを前にして手が止まる — 擬似言語は「読み方の約束」だけ
基本情報技術者試験の科目Bでは、擬似言語のプログラムを読み、変数の値や空欄に入る式を答える問題が出ます。初めて見ると身構えてしまいますが、擬似言語は特定のプログラム言語ではなく、IPAが決めた「読み方の約束」の集まりです。代入・if・while・forなど、覚える量は多くありません。
手が止まる原因の多くは、頭の中だけで変数の値を追いかけていることです。値の変化を紙に書き出せば、一行ずつ進められるようになります。
この単元では、記述形式、トレース表、データの置き方、探索と整列の手数を、数値で順に確認します。
IPAの記述形式を読み解く — ←・if・while・forの約束
基本情報技術者試験の擬似言語の記述形式は、IPAの「試験で使用する情報技術に関する用語・プログラム言語など」の別紙2にまとめられ、問題文に注記がない限り適用されます。主な約束を表にします。
| 記述形式 | 読み方 | 書き方の例 |
|---|---|---|
| 変数名 ← 式 | 式の値を計算して変数に代入する | 合計 ← 合計 + 3 |
| if (条件式) 〜 elseif (条件式) 〜 else 〜 endif | 条件式を上から評価し、最初に真になった処理だけを実行する | if (点数 ≧ 80) |
| while (条件式) 〜 endwhile | 条件式が真の間、処理を繰り返す(前判定) | while (i ≦ 5) |
| for (制御記述) 〜 endfor | 制御記述に従って処理を繰り返す | for (i を 1 から 5 まで 1 ずつ増やす) |
| 配列名[要素番号] | 配列の要素を指定する | A[3] |
最初に気をつけたいのは「←」の向きです。「合計 ← 合計 + 3」は数学の等式ではなく、今の合計に3を足した値を、合計に入れ直す操作を表します。右辺で使う合計は更新前の値で、実行後に左辺の変数が書き換わります。
if は「最初に真になった1つだけ」を実行します。たとえば if (点数 ≧ 80) の次が elseif (点数 ≧ 60) で、点数が 75 なら、75 ≧ 80 は偽、75 ≧ 60 は真なので elseif の処理だけを実行し、else には進みません。
もう1つの注意点は配列の要素番号です。何番から始まるかは問題文の注記で確認します。IPAの科目Bサンプル問題では「配列の要素番号は 1 から始まる」と注記されています。まず注記を読む習慣をつけると、先頭要素の取り違えを防げます。
トレース表で14になるまで手を動かす
手動実行の基本は、変数ごとに列を作るトレース表です。要素番号が 1 から始まる配列 A = {3, 1, 4, 1, 5} の合計を求める擬似言語を追います。
合計 ← 0
for (i を 1 から 5 まで 1 ずつ増やす)
合計 ← 合計 + A[i]
endfor
| 繰り返し | i | A[i] | 実行する式 | 実行後の合計 |
|---|---|---|---|---|
| 開始前 | - | - | 合計 ← 0 | 0 |
| 1回目 | 1 | 3 | 合計 ← 0 + 3 | 3 |
| 2回目 | 2 | 1 | 合計 ← 3 + 1 | 4 |
| 3回目 | 3 | 4 | 合計 ← 4 + 4 | 8 |
| 4回目 | 4 | 1 | 合計 ← 8 + 1 | 9 |
| 5回目 | 5 | 5 | 合計 ← 9 + 5 | 14 |
最終的な合計は 14 で、3 + 1 + 4 + 1 + 5 = 14 と一致します。「1行が1回の繰り返し」と決めておくと、値を見失いません。
表があると、読み違いの原因も逆算できます。「合計 ← A[i]」のように加算を代入と読むと、毎回上書きされて最後の A[5] である 5 だけが残ります。for を i = 4 までと読むと 3 + 1 + 4 + 1 = 9 になり、A[5] を足し忘れます。i = 2 から始まると読むと 1 + 4 + 1 + 5 = 11 になり、先頭の A[1] を飛ばします。
取り出す順番で選ぶ — 配列・スタック・キューと計算量
データ構造とは、データを入れる「入れ物の形」のことです。計算量の O(n) は、データが n 倍になると手数もおよそ n 倍になる増え方を表します。
| 構造 | 取り出し方 | 得意な操作 | 苦手な操作 |
|---|---|---|---|
| 配列 | 要素番号で直接指定する | 要素番号を指定した参照は O(1) | 先頭への挿入は後ろを全部ずらすので O(n) |
| 連結リスト | ポインタで次の要素をたどる | 挿入・削除は付け替えだけで O(1) | 探索は先頭からたどるので O(n) |
| スタック | 最後に入れたものから取り出す(LIFO) | push と pop | 途中の要素の取り出し |
| キュー | 最初に入れたものから取り出す(FIFO) | enqueue と dequeue | 後ろの要素の先取り |
配列の先頭に挿入する様子を数えてみましょう。要素番号 1 から 3 に {10, 20, 30} が入っていて、先頭に 5 を入れるとします。後ろから順に 30、20、10 を1つずつ後ろへ移し、空いた要素番号 1 に 5 を入れます。ずらした回数は 3 回で、要素数 n と同じです。
| 配列の要素数 n | 先頭への挿入でずらす回数 | 末尾への追加でずらす回数(空きがある場合) |
|---|---|---|
| 5 | 5 | 0 |
| 10,000 | 10,000 | 0 |
スタックは「積んだ本の山」で、push(6)、push(8)、pop、push(3)、pop、pop の順に操作すると、取り出される値は 8、3、6 の順です。同じ順に6、8、3を入れたキューなら、最初に取り出すのは 6 です。
半分に絞る — 線形探索と二分探索の比較回数
線形探索は、配列の先頭から順に1つずつ比べる方法で、整列されていないデータにも使えます。電話帳を先頭からめくる方法で、n 件なら最大 n 回の比較です。二分探索は整列済みの配列が前提で、中央の要素と比べて候補を半分に絞ります。電話帳を真ん中から開く方法です。
要素番号 1 から 15 に昇順で {2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44} が入っている配列から、29 を探します。中央の要素番号は(左端 + 右端)÷ 2 の商で求めます。
| 回 | 左端 | 右端 | 中央 | 中央の値 | 比較結果と次の範囲 |
|---|---|---|---|---|---|
| 1回目 | 1 | 15 | 8 | 23 | 29 は 23 より大きいので左端を 9 にする |
| 2回目 | 9 | 15 | 12 | 35 | 29 は 35 より小さいので右端を 11 にする |
| 3回目 | 9 | 11 | 10 | 29 | 一致したので探索を終える |
計算は(1 + 15)÷ 2 = 8、(9 + 15)÷ 2 = 12、(9 + 11)÷ 2 = 10 です。3回で見つかりました。線形探索なら 29 は要素番号 10 なので 10 回かかります。
二分探索の最大比較回数は、中央の要素を1回見るごとに1回と数えると、切り捨てた log2 n に 1 を足した値になります。
| 件数 n | 2の累乗との関係 | 最大比較回数 |
|---|---|---|
| 7 | 4 ≦ 7 < 8 なので 2 + 1 | 3回 |
| 15 | 8 ≦ 15 < 16 なので 3 + 1 | 4回 |
| 1,023 | 512 ≦ 1,023 < 1,024 なので 9 + 1 | 10回 |
| 1,024 | 1,024 ≦ 1,024 < 2,048 なので 10 + 1 | 11回 |
1,023 件から 1,024 件へ1件増えるだけで、最大比較回数は 10 回から 11 回になる点に注意してください。件数が2倍になっても、増えるのは1回だけです。
並べ替えの手数を数える — バブルソートと速い整列
バブルソートは、隣り合う2要素を比べて前のほうが大きければ交換する操作を、端から端まで繰り返す整列法です。1回のパスで最大の値が右端に落ち着きます。{5, 3, 4, 1, 2} を昇順に整列する全パスを追ってみましょう。
| パス | 比較と交換 | パス後の配列 | 交換回数 |
|---|---|---|---|
| 1 | 5と3、5と4、5と1、5と2をすべて交換 | 3, 4, 1, 2, 5 | 4 |
| 2 | 3と4は交換なし、4と1、4と2を交換 | 3, 1, 2, 4, 5 | 2 |
| 3 | 3と1、3と2を交換 | 1, 2, 3, 4, 5 | 2 |
| 4 | 1と2は交換なし | 1, 2, 3, 4, 5 | 0 |
交換回数は 4 + 2 + 2 + 0 = 8 回、比較回数は 4 + 3 + 2 + 1 = 10 回です。この 8 回は、元の並びで「大きい値が小さい値より前にある組」の数に一致します。5 の4組、3 の2組、4 の2組で、合計 8 組です。隣同士の交換は、逆順の組を1組ずつ解消するためです。
比較回数は n 個で n × (n − 1) ÷ 2 回なので、n = 1,000 なら 1,000 × 999 ÷ 2 = 499,500 回です。O(n log n) の整列なら 1,000 × 約10 = 約1万回で済み、約50倍の差があります。
速い整列法の代表がマージソートとクイックソートです。マージソートは配列を半分ずつに分け、整列済みの列を併合する方法で、入力の並びによらず O(n log n) です。同じ値の要素の元の順序が保たれる安定な整列でもあります。クイックソートは平均 O(n log n)、最悪 O(n²) で、安定ではありません。
出典:IPA『試験で使用する情報技術に関する用語・プログラム言語など Ver.5.1』別紙2 https://www.ipa.go.jp/shiken/syllabus/doe3um0000002djj-att/shiken_yougo_ver5_1.pdf 。
出典:IPA『基本情報技術者試験 科目B サンプル問題』 https://www.ipa.go.jp/shiken/syllabus/ps6vr7000000oett-att/fe_kamoku_b_sample.pdf 。
ここまでの要点 — 擬似言語とアルゴリズムを5分で復習
- 代入は「変数名 ← 式」で、右辺は更新前の値で計算します。繰り返しは for (i を 1 から 5 まで 1 ずつ増やす) 〜 endfor と while (条件式) 〜 endwhile です。
- 配列の要素番号の始まりは、各問題文の注記で確認します。
- トレース表は1行を1回の繰り返しにして、変数ごとに列を作ります。
- スタックは後入れ先出し(LIFO)、キューは先入れ先出し(FIFO)で、配列の先頭挿入は後ろをずらすので O(n) です。
- 二分探索は整列済みが前提で、最大比較回数は floor(log2 n) + 1 です。1,023 件は10回、1,024 件は11回です。
- バブルソートは O(n²)、マージソートは常に O(n log n) で安定です。
- 試験では、トレースで変数の最終値を問う問題、空欄の条件式を選ぶ問題、計算量や安定性を選ぶ問題として問われます。