テクノロジ系

データの置き方で速さが変わる — 配列・探索・整列と擬似言語のトレース

IPA擬似言語の記述形式の読み方、トレース表による手動実行、配列・スタック・キュー、線形探索と二分探索、整列アルゴリズムの計算量を学ぶ。

更新日 執筆: PassDojo 編集部

PR
目次読了目安 約9分
  1. 科目Bを前にして手が止まる — 擬似言語は「読み方の約束」だけ
  2. IPAの記述形式を読み解く — ←・if・while・forの約束
  3. トレース表で14になるまで手を動かす
  4. 取り出す順番で選ぶ — 配列・スタック・キューと計算量
  5. 半分に絞る — 線形探索と二分探索の比較回数
  6. 並べ替えの手数を数える — バブルソートと速い整列
  7. ここまでの要点 — 擬似言語とアルゴリズムを5分で復習

科目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

繰り返しiA[i]実行する式実行後の合計
開始前--合計 ← 00
1回目13合計 ← 0 + 33
2回目21合計 ← 3 + 14
3回目34合計 ← 4 + 48
4回目41合計 ← 8 + 19
5回目55合計 ← 9 + 514

最終的な合計は 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先頭への挿入でずらす回数末尾への追加でずらす回数(空きがある場合)
550
10,00010,0000

スタックは「積んだ本の山」で、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回目11582329 は 23 より大きいので左端を 9 にする
2回目915123529 は 35 より小さいので右端を 11 にする
3回目9111029一致したので探索を終える

計算は(1 + 15)÷ 2 = 8、(9 + 15)÷ 2 = 12、(9 + 11)÷ 2 = 10 です。3回で見つかりました。線形探索なら 29 は要素番号 10 なので 10 回かかります。

二分探索の最大比較回数は、中央の要素を1回見るごとに1回と数えると、切り捨てた log2 n に 1 を足した値になります。

件数 n2の累乗との関係最大比較回数
74 ≦ 7 < 8 なので 2 + 13回
158 ≦ 15 < 16 なので 3 + 14回
1,023512 ≦ 1,023 < 1,024 なので 9 + 110回
1,0241,024 ≦ 1,024 < 2,048 なので 10 + 111回

1,023 件から 1,024 件へ1件増えるだけで、最大比較回数は 10 回から 11 回になる点に注意してください。件数が2倍になっても、増えるのは1回だけです。

並べ替えの手数を数える — バブルソートと速い整列

バブルソートは、隣り合う2要素を比べて前のほうが大きければ交換する操作を、端から端まで繰り返す整列法です。1回のパスで最大の値が右端に落ち着きます。{5, 3, 4, 1, 2} を昇順に整列する全パスを追ってみましょう。

パス比較と交換パス後の配列交換回数
15と3、5と4、5と1、5と2をすべて交換3, 4, 1, 2, 54
23と4は交換なし、4と1、4と2を交換3, 1, 2, 4, 52
33と1、3と2を交換1, 2, 3, 4, 52
41と2は交換なし1, 2, 3, 4, 50

交換回数は 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) で安定です。
  • 試験では、トレースで変数の最終値を問う問題、空欄の条件式を選ぶ問題、計算量や安定性を選ぶ問題として問われます。