プログラミング言語を整える
中級アルゴリズムを整える。
＝ 並べ替え・探し方・しまい方を図で
先に結論
アルゴリズムは「仕事の手順書」、データ構造は「データのしまい方」です。同じ結果でも、手順としまい方しだいで手間が何十倍も変わります。
たとえば1,000件から1件を探すとき、端から順に見ると最大1,000回、並んだデータを半分ずつ絞ると最大10回で済みます。下の3つの章で、それぞれ手を動かして確かめられます。
基本情報技術者試験（FE）の科目B は、擬似言語のプログラムを1行ずつ追う問題です。配列の添字が 1 から始まる点が Java（0 から）と違うので、図の添字の数え方に気をつけて読んでください。試験の分野ごとの道具は基本情報・ITパスポートの範囲マップにまとめています。
ソート：棒の高さで並べ替えを見る
数の並びを小さい順に整える手順がソートです。棒の高さが数の大きさ。1手ずつ進めて、いま何を比べ、何を入れ替えたのかを確かめます。
やり方
隣どうしを比べ、左が大きければ入れ替える。これを端から端まで繰り返すと、大きい値が右端に1つずつ落ち着く。
- まだ
- 比較「比」
- 交換・書き込み「換」「書」
- 最小候補「最」・ピボット「基」・取り出し「選」
- 確定「✔」
- 比べた回数
- 0
- 動かした回数
- 0
動かした回数は、交換1回を1、配列への代入（ずらす・書き戻す）1回を1と数えます。同じ位置どうしは動かしていないので数えません。
疑似コード（バブルソート・光っている行がいま実行中）
a は配列、n は個数、swap(a, x, y) は a の x 番目と y 番目の入れ替え。コードの添字は Java と同じ0始まり。
同じデータで5つを走らせると
上で作ったデータをそのまま5つに渡したときの回数です。「データを作り直す」や並び方の切り替えで変わります。
| やり方 | 比べた回数 | 動かした回数 | 比べた回数の目安 |
|---|
計算量（O 記法）の比べ表
O 記法は「データの個数 n が増えたとき、手間がどう増えるか」を表す書き方です。 n が2倍になると、O(n) の手間は2倍、O(n log n) は2倍より少し多く、O(n²) は4倍になります。 細かい係数は無視して、増え方の形だけを見ます。
| 個数 n | n（O(n)） | n log₂n（約） | n²（O(n²)） |
|---|---|---|---|
| 10 | 10 | 33 | 100 |
| 100 | 100 | 664 | 10,000 |
| 1,000 | 1,000 | 9,966 | 1,000,000 |
| やり方 | 最良 | 平均 | 最悪 | 安定 | 追加メモリ |
|---|---|---|---|---|---|
| バブルソート | O(n) | O(n²) | O(n²) | 安定 | O(1) |
| 選択ソート | O(n²) | O(n²) | O(n²) | 安定ではない | O(1) |
| 挿入ソート | O(n) | O(n²) | O(n²) | 安定 | O(1) |
| クイックソート | O(n log n) | O(n log n) | O(n²) | 安定ではない | O(log n) |
| マージソート | O(n log n) | O(n log n) | O(n log n) | 安定 | O(n) |
- バブルソート 最良の O(n) は、交換がなければ途中で終える書き方をした場合。
- 選択ソート 比較の回数はデータの並びによらない。交換は多くても n−1 回。
- 挿入ソート ほぼ整列済みのデータでは比較が少なくて済む。
- クイックソート ピボットの選び方が悪いと最悪になる（ここでは右端固定なので、整列済み・逆順で最悪）。追加メモリは再帰の深さ（最悪 O(n)）。
- マージソート 作業用の配列が n 個ぶん必要。
「安定」とは、同じ値が複数あるとき、並べ替えたあとも元の前後関係が保たれることです。 たとえば得点でソートしたあと、同点の人を元の名簿順のままにしておきたいときに関わります。
探して見つける：線形探索と二分探索
並んだデータの中から、探している値を見つける方法を 2 つ。同じデータ・同じ値で同時に走らせて、何回で見つかるかを見比べます。
たとえると
線形探索は、名簿を先頭から 1 行ずつ指でなぞって名前を探すやり方です。二分探索は、五十音順の辞書を真ん中あたりで開き、「探す語はそれより前か後か」で半分ずつ捨てていくやり方です。辞書のように順番に並んでいるからこそ、半分を捨てられます。
探す値を選ぶ
線形探索（先頭から順に）
比較 0 回
二分探索（真ん中で半分に絞る）
比較 0 回
見かた：× は調べて外れた位置、調べ中 はいま比べている位置、一致 は見つかった位置。二分探索では、薄く点線になった範囲は「もう探さない」と決まった部分で、low・mid・high が今の範囲の左端・真ん中・右端です。▶ の付いた行がいま実行している行です。
データが増えたとき、最大で何回比べるか
線形探索は、運が悪いと最後まで（または見つからないと全部）調べるので、最大で n 回です。二分探索は 1 回ごとに候補が半分になるので、最大で ⌊log₂ n⌋ + 1 回です（⌊ ⌋ は小数点以下の切り捨て）。データが 2 倍になると、線形探索の最大は 2 倍、二分探索の最大は 1 回増えるだけです。
| 個数 n | 線形探索の最大 | 二分探索の最大 | 長さの比べ（n = 1,000 を 100% とした棒） |
|---|---|---|---|
| 8 | 8 回 | 4 回 | |
| 16 | 16 回 | 5 回 | |
| 32 | 32 回 | 6 回 | |
| 64 | 64 回 | 7 回 | |
| 100 | 100 回 | 7 回 | |
| 200 | 200 回 | 8 回 | |
| 500 | 500 回 | 9 回 | |
| 1,000 | 1,000 回 | 10 回 | |
| 1,000,000 | 1,000,000 回 | 20 回 | 棒にすると二分探索は見えないほど短い |
棒は上が線形探索（灰）、下が二分探索（青）。n が大きいほど差が開きます。
データ構造を手で動かす
データのしまい方には種類があり、得意なこと・苦手なことが違います。ボタンで操作すると、中で何が起きたかを 1 手ずつ図と言葉で見られます。
配列（同じ大きさの箱を横に並べる）
番号（添字）を言えば、一発でその箱の中身を取り出せる並びです。途中に 1 つ入れたいときは、後ろの全員を 1 つずつずらして場所をあける必要があります。
Java や C では添字は 0 から数えますが、基本情報技術者試験の科目Bの擬似言語では 1 から数えます。切り替えると、下の説明も擬似コードもその数え方に変わります。
擬似コード（実行中の行に ▶ が付きます）
得意なこと 添字で読む・書くのは 1 回で済みます（O(1)）。メモリ上で隣り合って並ぶので、まとめて処理するのも速いです。
苦手なこと 途中への挿入・削除は後ろをずらすので、要素数に比例して手間が増えます（O(n)）。大きさは作るときに決まります。
連結リスト（次のノードの場所を持つ鎖）
値と「次はここ」という矢印（ポインタ）をセットにしたノードを、鎖のようにつないだものです。途中に入れるときは、矢印を付け替えるだけでほかのノードは動きません。
擬似コード（実行中の行に ▶ が付きます）
得意なこと 先頭への挿入・削除は矢印の付け替えだけで済みます（O(1)）。手前のノードが分かっていれば、途中でも付け替えは 2 本で済みます。
苦手なこと n 番目を読むにも、値を探すにも、先頭から順にたどる必要があります（O(n)）。矢印を持つぶん、メモリも余分に使います。
スタック（積み上げて、上から取る）
本を積み重ねるように、入れるのも出すのもいちばん上だけです。最後に入れたものが最初に出てくるので、後入れ先出し（LIFO）と呼びます。ブラウザの「戻る」や、関数呼び出しの記録に使われます。
擬似コード（実行中の行に ▶ が付きます）
得意なこと push も pop も、動かすのは top の 1 か所だけです（O(1)）。
苦手なこと 真ん中や底にあるものは、上のものを先に取らないと取り出せません。
キュー（並んだ順に出る行列）
お店の行列のように、入るのは後ろ、出るのは前です。先に入れたものが先に出るので、先入れ先出し（FIFO）と呼びます。印刷の順番待ちなどに使われます。
擬似コード（実行中の行に ▶ が付きます）
得意なこと enqueue も dequeue も、先頭と末尾の印を動かすだけです（O(1)。リング状の配列や連結リストで作った場合）。
苦手なこと 途中の要素を取り出すことはできません。順番どおりにしか出せません。
二分探索木（小さい値は左、大きい値は右）
各ノードが「左の子は自分より小さい、右の子は自分より大きい」という約束を守って並んだ木です。探すときは、比べるたびに半分近くを切り捨てて進めます。
擬似コード（実行中の行に ▶ が付きます）
得意なこと 木の形が整っていれば、探索・挿入・削除は段数に比例した回数で済みます（平均 O(log n)）。中順で巡回すると昇順に取り出せます。
苦手なこと 昇順に入れ続けるなど木が一方に偏ると、連結リストと同じ並びになり O(n) まで遅くなります。
ハッシュテーブル（キーから置き場所を計算する）
キーをハッシュ関数に通して「この番号の箱に入れる」と計算で決める仕組みです。探すときも同じ計算をするので、全部を見て回る必要がありません。別々のキーが同じ番号になることを「衝突」と呼びます。
ハッシュ関数は「数字だけのキーは、その数を表の大きさで割った余り」「それ以外は、各文字の文字コードを足した合計を表の大きさで割った余り」と決めています。例: "AB" は 65 + 66 = 131、131 を 7 で割った余り 5。
擬似コード（実行中の行に ▶ が付きます）
得意なこと うまく散らばれば、入れる・探す・消すが 1 回の計算でほぼ済みます（平均 O(1)）。
苦手なこと 衝突が増えると遅くなり、全部が同じ番号になると O(n) まで落ちます。キーを順番に取り出すのは苦手です。
このツールについて
並べ替え・探し方・データのしまい方を、ボタンで1手ずつ動かして、中で何が起きているかを図で確かめます。計算はすべてこの端末の中で行い、どこにも送信しません。
ソート5種・二分探索・データ構造6種を、ボタンで1手ずつ動かして図で確かめます。比べた回数・入れ替えた回数も数えます。言語は Java とあわせてどうぞ。
主な機能
- 5つのソートを棒グラフで1手ずつ再生し、比較・交換の回数を数える
- 計算量（O記法）の最良・平均・最悪・安定性を比べる表
- 線形探索と二分探索の回数比べと、データ数ごとの最大回数
- 配列・連結リスト・スタック・キュー・二分探索木を操作して図で確かめる
- ハッシュテーブルの衝突処理（チェイニングとオープンアドレス）を切り替えて比べる
よくある質問
Q. アルゴリズムとデータ構造は何が違いますか？
A. アルゴリズムは「仕事の手順」、データ構造は「データのしまい方」です。たとえば二分探索という手順は、データが順番に並んでしまわれていて初めて使えます。両方をセットで考えます。
Q. O(n log n) のような書き方は何を表していますか？
A. データの数 n が増えたとき、手間がどのくらいの勢いで増えるかの目安です。O(n²) はデータが2倍になると手間が約4倍、O(n log n) は2倍強で済みます。細かい定数は省いて、増え方の形だけを比べます。
Q. どのソートを使えばよいですか？
A. 実務では言語の標準のソート（Java なら Arrays.sort や Collections.sort）を使います。ここで5つを比べるのは、手間の違いが生まれる理由を知り、試験や設計で計算量を判断できるようにするためです。
Q. 基本情報技術者試験（FE）の科目B 対策に使えますか？
A. 科目B はプログラムを1行ずつ追って変数の値を答える問題が中心です。ソートや二分探索、スタック・キュー・木の操作を1手ずつ動かして追う練習に使えます。FE の擬似言語では配列の添字が1から始まる点に注意してください。
Q. 二分探索はいつでも使えますか？
A. データが小さい順（または大きい順）に並んでいるときだけ使えます。並んでいないデータでは、先にソートするか、端から順に探す線形探索を使います。
入力値はURLの「#」以降に入るためサーバーには送信されません。リンクを開くと同じ状態を復元します。
続けて整える
このツールの解説記事
この内容は、研修でも扱っています
totonoe.tech を運営する株式会社Koinobori は、法人向けの研修サービス「NOBORIBA®」も運営しています。 ここで手を動かした内容を、講師から教わる形の研修です。このページの道具は無料のまま、登録もいりません。
