· theory · 9 min read
線形探索・二分探索・バブルソートとは？基本情報技術者試験のアルゴリズム基礎
線形探索・二分探索・バブルソート・選択ソートとO記法——基本情報技術者試験の科目Bで必ず問われるアルゴリズム基礎4種の仕組みと計算量を、擬似言語の読み方と合わせて解説する。
アルゴリズムとは「問題を解く手順の定義」だ。 同じ問題を解くにも「速いやり方」と「遅いやり方」があり、その差を測る物差しが計算量（O記法）だ。
基本情報技術者試験では、アルゴリズムの知識は科目A（選択問題）と科目B（擬似言語トレース）の両方に登場する。 「どんな手順で動くか」を自分の頭でトレースできるレベルまで理解しておくことが合格の条件だ。
探索アルゴリズム — データを「見つける」手順
線形探索
配列の先頭から順番に目的の値を探す、最もシンプルな探索アルゴリズムだ。
手順:
1. 先頭の要素から比較を始める
2. 目的の値と一致したら終了（見つかった）
3. 末尾まで到達しても見つからなければ「存在しない」特徴
- 配列がソートされていなくても使える
- 最悪の場合、全要素を調べる必要がある
- 計算量：O(n)（nはデータ件数）
「10,000件のデータから1件を探す場合、最悪で10,000回比較が必要」ということだ。
試験では「以下の配列から値42を線形探索で見つけるとき、何回目の比較で見つかるか」という問題が出る。単純に先頭から数えるだけだが、インデックスが1始まりであることを忘れずに。
二分探索
ソート済みの配列に対して使える、高速な探索アルゴリズムだ。 配列の真ん中の要素と比較し、目的の値が大きければ右半分、小さければ左半分だけに絞り込む。
手順（配列が昇順ソート済みとして）:
1. left=1, right=配列の末尾 とする
2. mid = (left + right) ÷ 2（整数部分）を求める
3. array[mid] と目的値を比較する
- 一致 → 見つかった、終了
- 目的値 < array[mid] → right = mid - 1（左半分を探索）
- 目的値 > array[mid] → left = mid + 1（右半分を探索）
4. left > right になったら「存在しない」特徴
- ソート済みデータが前提（事前にソートが必要）
- 探索のたびに対象範囲が半分になる
- 計算量：O(log n)
「10,000件のデータなら最大14回の比較で見つかる」（log₂10000 ≈ 13.3）。 線形探索の最悪10,000回と比べると、差は圧倒的だ。
試験では「二分探索の途中経過で mid の値がどう変わるか」をトレースする問題が頻出だ。 left・right・mid の3つの変数を紙に書きながら追う練習をしておくこと。
整列アルゴリズム — データを「並べ替える」手順
バブルソート
隣り合う2つの要素を比較して、大小が逆なら交換する。 これを配列全体に対して繰り返すと、最大値が泡（バブル）のように末尾へ浮かび上がっていく。
手順（昇順ソートの場合）:
1. i=1 から n-1 まで繰り返す
2. j=1 から n-i まで繰り返す
3. array[j] > array[j+1] なら swap（入れ替え）特徴
- 実装がシンプルで理解しやすい
- 比較回数が多く処理が遅い
- 計算量：O(n²)
試験でのトレースポイントは「何回目のパスで配列がどう変化するか」だ。 1パス（外側ループ1回）ごとに末尾から1つずつ最大値が確定するイメージを持つと追いやすい。
スワップ処理の擬似言語はほぼ必ず以下の形で出る。
tmp ← array[j]
array[j] ← array[j+1]
array[j+1] ← tmptmpなしで直接入れ替えると値が失われる。このパターンを体に染み込ませておくこと。
選択ソート
未整列部分の中から最小値（または最大値）を探し、先頭要素と交換する。 これを繰り返して整列する。
手順（昇順ソートの場合）:
1. i=1 から n-1 まで繰り返す
2. minIndex = i とする
3. j=i+1 から n まで繰り返す
4. array[j] < array[minIndex] なら minIndex = j
5. array[i] と array[minIndex] を swap特徴
- 比較回数はバブルソートと同じだが交換回数が少ない
- 計算量：O(n²)
- 「交換が少ない」という点でバブルソートと区別できることが重要
試験では「バブルソートと選択ソートの違い」を問う選択問題が出る。 「バブルソートは隣接要素を繰り返し交換、選択ソートは最小値を選んで一度だけ交換」という差を押さえておくこと。
計算量O記法の基本
アルゴリズムの「速さ」を比較するための表記法だ。データ件数 n が増えたとき、処理時間がどう増えるかを表す。
| O記法 | 意味 | 代表的なアルゴリズム |
|---|---|---|
| O(1) | データ数に無関係で一定 | 配列への直接アクセス |
| O(log n) | 対数的に増加（非常に速い） | 二分探索 |
| O(n) | データ数に比例して増加 | 線形探索 |
| O(n log n) | やや速いソート | クイックソート・マージソート |
| O(n²) | データ数の2乗で増加（遅い） | バブルソート・選択ソート |
試験では「以下のアルゴリズムの計算量はどれか」という選択問題で使う。 O(n²) と O(n log n) の差が大きいことを数値イメージで持っておくと選択問題が速くなる。 n=1000 の場合、O(n²)は100万回、O(n log n)は約10,000回の処理回数になる。
AIで練習する方法
アルゴリズムのトレースは「自分で手を動かした回数」が理解度に直結する。以下のプロンプトで練習問題を無限に作れる。
基本情報技術者試験の科目B形式で、以下の問題を作ってください。
対象アルゴリズム: バブルソート
配列: [8, 3, 6, 1, 5]
問題形式: 1パス目が終了した時点での配列の状態を答えよ
擬似言語の添字は1始まりで記述すること答えを出した後で「自分の解答が正しいか採点してください」と続けると即時フィードバックが得られる。
まとめ
| アルゴリズム | 種別 | 前提条件 | 計算量 | 試験ポイント |
|---|---|---|---|---|
| 線形探索 | 探索 | なし | O(n) | 先頭から何番目で見つかるか |
| 二分探索 | 探索 | ソート済み | O(log n) | left/mid/rightの変化を追う |
| バブルソート | 整列 | なし | O(n²) | 隣接swap・1パス後の状態 |
| 選択ソート | 整列 | なし | O(n²) | 最小値選択・交換回数の少なさ |
4つのアルゴリズムは仕組みを理解してしまえば、擬似言語に書き換えられても動きを追える。用語の暗記より「手を動かしてトレース」を優先してほしい。
