アルゴリズム

ねらい

問題を解く手順であるアルゴリズムの基本を学びます。このレッスンを終えると、流れ図の考え方、探索と整列の代表的なアルゴリズムの仕組みと使い分け、再帰と分割統治法の考え方を説明できるようになります。

アルゴリズムとその表現

アルゴリズムは、誰が実行しても同じ結果になるように明確に定めた、問題を解くための手順です。手順の表現には、記号を線でつないで図にする流れ図（フローチャート）、プログラムに近い書き方の擬似言語、条件と動作の組合せを表にする決定表（デシジョンテーブル）が使われます。

流れ図では、開始と終了を表す端子、処理、条件で道が分かれる判断、繰返しの範囲を示すループ端などの記号を使います。どんなに複雑な手順も、上から順に実行する順次、条件で分ける判定、同じ処理を繰り返す繰返しという3つの組合せで表せます。

擬似言語のトレース

擬似言語は、次のような決まった書き方で手順を表します（基本情報技術者試験 科目Bの冒頭に掲載される記述形式）。

擬似言語の問題を解く近道は、上から順に、実際に値を書き出しながら追うことです。これをトレースといいます。次のプログラムでトレースの手順を見てみましょう。整数型の配列 data の末尾の要素を先頭へ移動し、それ以外の要素は1つずつ後ろへずらします。

整数型の配列: data ← {1, 2, 3, 4, 5}
整数型: top, i
整数型: len ← dataの要素数
top ← data[len]
for (i を ○○○)
  data[i] ← data[i － 1]
endfor
data[1] ← top

○○○には、「len から 2 まで 1 ずつ減らす」と「2 から len まで 1 ずつ増やす」のどちらが入るでしょうか。トレースして確かめます。data = {1, 2, 3, 4, 5}（len = 5）としたときの動きを、両方の向きで追ってみます。

後ろから減らす場合（i = 5 → 4 → 3 → 2）

末尾の5が先頭に移り、残りは1つずつ後ろへ正しくずれました。

前から増やす場合（i = 2 → 3 → 4 → 5）を試すと

前から書き換えると、まだ使っていない値まで上書きしてしまい、元の2・3・4が失われます。正解は「len から 2 まで 1 ずつ減らす」です。

トレースは、正解の手順を確かめるだけでなく、間違った手順を試して、なぜ間違うかを確かめるときにも使えます。ループの向きで迷ったら、両方を小さいデータで実際に手を動かして比べるのが確実です。

この問題は、基本情報技術者試験の令和8年度公開問題（科目B 問1）そのものです。実際に解いてみたい場合は、この教材の問題一覧から挑戦できます。

探索のアルゴリズム：目的の値を見つける

線形探索法と2分探索法

線形探索法は、先頭から1件ずつ順に調べる素朴な方法です。どんな並び順のデータにも使えますが、1,000件のデータなら平均でおよそ500回の比較が必要です。

2分探索法は、冒頭の辞書引きと同じ方法です。整列済みのデータの真ん中と比べ、目的の値が前半にあるか後半にあるかを判断して、探す範囲を半分に絞ることを繰り返します。1,000件のデータでも最大10回ほどの比較で見つかります。ただし、データがあらかじめ整列されていることが前提です。

ハッシュ表探索法

ハッシュ表探索法は、値から計算式（ハッシュ関数）で格納場所を割り出し、原則1回の計算で目的の場所へ直行する方法です。異なる値が同じ場所に割り当たる衝突への対処が必要ですが、うまく働けば探索はデータ件数によらずほぼ一定の速さになります。

具体例で見てみましょう。格納場所を7個用意し、キーを7で割った余りをハッシュ値（格納場所の番号）とするハッシュ関数 ハッシュ値 ← キー mod 7 を使います。

キー10とキー24は、どちらもハッシュ値が3になります。これが衝突です。異なるキーが同じ格納場所を取り合ってしまいます。

衝突への代表的な対処法の一つが、同じ格納場所に複数の値をリストでつなげておく方法です。格納場所3には10と24の両方をつなげておき、探すときはハッシュ値で格納場所を特定したあと、つながったリストの中を順に見ていきます。衝突が少なければリストは短いままなので、探索の速さはほとんど落ちません。

整列のアルゴリズム：データを並べ替える

データを小さい順などに並べ替える処理を整列（ソート）といいます。仕組みが単純なものと、工夫で高速化したものに分けて押さえましょう。

単純な整列

いずれも仕組みは分かりやすいものの、データ件数が増えると比較回数はおよそ件数の2乗に比例して増えます。シェルソートは、一定の間隔を空けた要素どうしを先に整列しておくことで挿入ソートを改良したものです。

高速な整列

再帰と分割統治法

自分自身を呼び出して問題を解く書き方を再帰といいます。たとえば階乗の計算は、「5の階乗は、5かける4の階乗」というように、同じ形の一回り小さい問題に帰着できます。小さくなりきったところで答えを確定させ、順に戻りながら全体の答えを組み立てます。

大きな問題を小さな問題に分割し、それぞれを解いて組み合わせる設計方針を分割統治法といいます。クイックソートとマージソートは、分割統治法を再帰で実現した代表例です。

グラフや文字列を扱うアルゴリズム

グラフのアルゴリズム

駅と路線のようなつながりを表すグラフをたどる方法にも、行けるところまで深く進む深さ優先探索と、近い節から順に広げる幅優先探索があります。また、経路に距離や運賃のような重みがあるとき、最短経路を求める代表的な方法がダイクストラ法です。負の重みがある場合にも使える方法としてベルマンフォード法があります。乗換案内やカーナビの経路探索は、この最短経路探索の応用です。

文字列・ファイル・自然言語の処理

文章の中から目的の語を見つけ出す処理を文字列照合といいます。業務のバッチ処理では、整列や併合に加えて、部署コードなどのキーの変わり目ごとに集計を区切るコントロールブレーク処理が使われます。また、人間の言葉をコンピュータで扱う自然言語処理では、文を単語に区切る形態素解析、連続するn個のまとまりで文字列を捉えるn-gramといった手法が、情報検索や機械翻訳の土台になっています。

例題

次の問いに答えてください。

問1 2分探索法を使うために、探索対象のデータが満たしていなければならない前提は何ですか。

問2 1,000件のデータから線形探索法で目的の1件を探すとき、比較回数は平均でおよそ何回になりますか。

解答と解説

問1の答えは、データが整列済みであることです。2分探索法は「真ん中と比べて前半か後半かを決める」方法なので、並び順に規則がなければ範囲を絞れません。

問2の答えはおよそ500回です。線形探索法は先頭から順に調べるため、目的のデータが平均して真ん中あたりで見つかるとすると、件数の半分ほどの比較が必要になります。同じ1,000件でも、整列済みなら2分探索法で最大10回ほどで見つかります。ここに手順の工夫の威力が表れます。

応用

本試験を意識した問題を解いてみましょう。

問 整列アルゴリズムのうち、基準値を決めて、それより小さい要素の組と大きい要素の組に分割することを繰り返す方法はどれでしょうか。次の中から選んでください。

1. バブルソート
2. 選択ソート
3. 挿入ソート
4. クイックソート

解答と解説

答えは4のクイックソートです。基準値による分割を繰り返す分割統治法の代表的な整列アルゴリズムです。1のバブルソートは隣り合う要素の比較と交換を繰り返す方法、2の選択ソートは未整列部分から最小の要素を選んで先頭と交換していく方法、3の挿入ソートは整列済みの部分へ要素を正しい位置に差し込んでいく方法であり、いずれも基準値による分割は行いません。