代表的なアルゴリズム

代表的なアルゴリズムを学ぶ意味

前の節で、アルゴリズムの基本構造（順次・選択・繰返し）を学びました。この節では、それらを組み合わせて作られる代表的なアルゴリズムを見ていきます。

コンピュータが日々行っている処理の多くは、「大量のデータの中から目的のものを見つける（探索）」と「データを決まった順番に並べ替える（整列）」の2つに集約されます。たとえば、検索エンジンで調べ物をするのは探索ですし、成績順に名簿を並べ替えるのは整列です。さらに、複数のデータをまとめる「併合（マージ）」もよく使われます。

これらの処理には、目的は同じでも手順が異なるさまざまなアルゴリズムが存在します。どのアルゴリズムを選ぶかによって、処理の速さや前提条件が変わります。ITパスポート試験では、各アルゴリズムの仕組みの違いと使い分けの理由を理解しているかが問われます。

探索アルゴリズム

探索（サーチ）とは、たくさんのデータの中から目的のデータを見つけ出す処理です。たとえば、電話帳から「山田太郎」さんの電話番号を探すような場面をイメージしてください。

ここでは、ITパスポート試験で出題される2つの探索アルゴリズムを学びます。

線形探索法（逐次探索法）

線形探索法（リニアサーチ）は、データの先頭から順番に1つずつ調べていく、最もシンプルな探索アルゴリズムです。逐次探索法とも呼ばれます。

たとえば、次の配列から「8」を探す場合を考えましょう。

配列: [5, 3, 8, 1, 4]

まず先頭の 5 を調べる → 8ではない
次の 3 を調べる → 8ではない
次の 8 を調べる → 見つかった！

このように、先頭から1つずつ順に比較していき、目的の値が見つかるか、最後まで調べ終わるまで続けます。

線形探索法の特徴は次のとおりです。

データがソート（整列）されていなくても使える
仕組みが単純で理解しやすい
データの数が多くなると、最悪の場合すべてのデータを調べる必要があるため、処理に時間がかかる（計算量はデータの件数に比例）

2分探索法（バイナリサーチ）

2分探索法（バイナリサーチ）は、あらかじめ昇順または降順にソートされたデータに対して使える、高速な探索アルゴリズムです。

2分探索法の手順は、次のとおりです。

データの真ん中の要素と探したい値を比較する
一致すれば探索終了
探したい値のほうが大きければ、後ろ半分だけを対象にする
探したい値のほうが小さければ、前半分だけを対象にする
残ったデータに対して同じ手順を繰り返す

具体例で見てみましょう。昇順にソートされた配列から「7」を探します。

配列: [1, 3, 5, 7, 9, 11, 13]

真ん中の要素は 7（4番目）→ 探したい値 7 と一致 → 見つかった！

では、同じ配列から「11」を探す場合はどうでしょう。

真ん中の 7 と比較 → 11 > 7 なので後ろ半分 [9, 11, 13] に絞る
その真ん中の 11 と比較 → 見つかった！

このように、1回の比較でデータを半分に絞り込めるため、データの件数が増えても比較回数はゆるやかにしか増えません。たとえば1,000件のデータでも、線形探索法なら最大1,000回の比較が必要ですが、2分探索法なら約10回の比較で済みます。

試験で出るポイント

2分探索法はデータがソート済みであることが前提です。試験では「ソートされていないデータに2分探索法を使えるか」という観点で問われることがあります。答えは「使えない」です。

線形探索法と2分探索法の比較

比較項目	線形探索法	2分探索法
別名	逐次探索法	バイナリサーチ
仕組み	先頭から順に1つずつ比較	真ん中と比較して半分に絞る
データのソート	不要	必要（昇順または降順）
探索速度	遅い（データ件数に比例）	速い（比較回数が少ない）
向いている場面	データが少ない、未整列のデータ	データが多い、整列済みのデータ

試験で出るポイント

線形探索法と2分探索法の違いは頻出テーマです。特に「ソートが必要かどうか」と「探索速度の違い」の2点を確実に押さえましょう。

整列アルゴリズム（ソート）

整列（ソート）とは、データをある規則に従って順番に並べ替える処理です。小さい値から大きい値の順に並べることを昇順、大きい値から小さい値の順に並べることを降順と呼びます。

たとえば、[5, 3, 8, 1, 4] を昇順に整列すると [1, 3, 4, 5, 8] になります。

整列にもさまざまなアルゴリズムがあり、それぞれ手順や速さが異なります。ここでは、ITパスポート試験で問われるバブルソート、選択ソート、クイックソートの3つを学びます。

バブルソート

バブルソートは、隣り合う2つの要素を比較し、順序が逆なら入れ替える操作を端から端まで繰り返す整列アルゴリズムです。小さい値が泡（バブル）のように浮かび上がっていく様子から、この名前が付けられました。

具体的な数値でトレース（手順を追跡）してみましょう。[5, 3, 8, 1, 4] を昇順に整列します。

【1回目の走査】 左端から隣り合う要素を比較・交換していきます。

[5, 3, 8, 1, 4]  → 5と3を比較 → 5 > 3 なので交換
[3, 5, 8, 1, 4]  → 5と8を比較 → 5 < 8 なのでそのまま
[3, 5, 8, 1, 4]  → 8と1を比較 → 8 > 1 なので交換
[3, 5, 1, 8, 4]  → 8と4を比較 → 8 > 4 なので交換
[3, 5, 1, 4, 8]  ← 1回目終了：最大値の8が右端に確定

【2回目の走査】 右端の8は確定済みなので、残りの部分を同様に処理します。

[3, 5, 1, 4, 8]  → 3と5を比較 → そのまま
[3, 5, 1, 4, 8]  → 5と1を比較 → 交換
[3, 1, 5, 4, 8]  → 5と4を比較 → 交換
[3, 1, 4, 5, 8]  ← 2回目終了：5が確定

【3回目の走査】

[3, 1, 4, 5, 8]  → 3と1を比較 → 交換
[1, 3, 4, 5, 8]  → 3と4を比較 → そのまま
[1, 3, 4, 5, 8]  ← 3回目終了：4が確定

【4回目の走査】

[1, 3, 4, 5, 8]  → 1と3を比較 → そのまま
[1, 3, 4, 5, 8]  ← 4回目終了：すべて確定！

結果は [1, 3, 4, 5, 8] となり、昇順に整列されました。

バブルソートは仕組みがとてもシンプルですが、比較と交換の回数が多いため、データの件数が増えると処理が遅くなります。

試験で出るポイント

バブルソートでは、1回の走査で最大値（または最小値）が端に確定することを理解しておきましょう。トレース問題では、各ステップで配列がどう変化するかを丁寧に追うことが大切です。

選択ソート

選択ソートは、データの中から最大値（または最小値）を「選択」し、所定の位置の要素と交換する操作を繰り返す整列アルゴリズムです。

昇順に並べる場合の手順を、[5, 3, 8, 1, 4] で見てみましょう。ここでは「最小値を選んで先頭側と交換する」方法で説明します。

【1回目】 全体 [5, 3, 8, 1, 4] から最小値 1 を探す → 先頭の 5 と交換

[1, 3, 8, 5, 4]  ← 1が先頭に確定

【2回目】 残り [3, 8, 5, 4] から最小値 3 を探す → すでに先頭にあるので交換不要

[1, 3, 8, 5, 4]  ← 3が確定

【3回目】 残り [8, 5, 4] から最小値 4 を探す → 8 と交換

[1, 3, 4, 5, 8]  ← 4が確定

【4回目】 残り [5, 8] から最小値 5 を探す → すでに先頭にあるので交換不要

[1, 3, 4, 5, 8]  ← すべて確定！

選択ソートの特徴は、交換の回数が少ない点です。1回の走査で交換は最大1回だけです。一方で、毎回すべての未整列部分を走査して最小値（または最大値）を見つける必要があるため、比較回数はバブルソートと同程度です。

試験で出るポイント

選択ソートでは「最大値を選んで末尾と交換」「最小値を選んで先頭と交換」のどちらの手順でも出題されます。問題文をよく読んで、どちらの方式かを確認しましょう。

クイックソート

クイックソートは、データの中から1つの基準値（ピボット）を選び、ピボットより小さいグループと大きいグループに分割する操作を繰り返す整列アルゴリズムです。名前のとおり、一般的に他のソートアルゴリズムより高速に動作します。

手順のイメージを [5, 3, 8, 1, 4] で見てみましょう。ピボットとして 5 を選んだとします。

【1回目の分割】

5より小さい: [3, 1, 4]
ピボット: 5
5より大きい: [8]

【2回目の分割】 左のグループ [3, 1, 4] に対してピボット 3 を選ぶ

3より小さい: [1]
ピボット: 3
3以上: [4]

すべてのグループが1個以下になったので分割終了です。結果をつなげると [1, 3, 4, 5, 8] になります。

クイックソートの特徴をまとめます。

平均的な処理速度が速い（バブルソートや選択ソートより高速）
ピボットの選び方によって効率が変わる
データを分割しながら整列するため、「分割統治法」に基づくアルゴリズムと言えます

整列アルゴリズムの比較

比較項目	バブルソート	選択ソート	クイックソート
仕組み	隣り合う要素を比較・交換	最大値（最小値）を選んで端と交換	ピボットで分割を繰り返す
処理速度	遅い	遅い	速い
特徴	仕組みが最もシンプル	交換回数が少ない	平均的に最も高速

試験で出るポイント

3つの整列アルゴリズムの中で、クイックソートが最も高速であることを覚えておきましょう。バブルソートと選択ソートは仕組みの違い（隣り合う要素を交換 vs 最大値・最小値を選んで交換）を区別できるようにしておくことが大切です。

併合（マージ）

**併合（マージ）**とは、すでに整列されている複数のデータ列を、整列された状態を保ったまま1つにまとめる処理です。

たとえば、2つの昇順に整列されたデータ列をマージする場合を考えましょう。

データ列A: [1, 4, 7]
データ列B: [2, 5, 6]

手順は次のとおりです。

AとBの先頭を比較 → 1 < 2 なので 1 を取り出す → 結果: [1]
Aの次（4）とBの先頭（2）を比較 → 2 < 4 なので 2 を取り出す → 結果: [1, 2]
Aの先頭（4）とBの次（5）を比較 → 4 < 5 なので 4 を取り出す → 結果: [1, 2, 4]
Aの次（7）とBの先頭（5）を比較 → 5 < 7 なので 5 を取り出す → 結果: [1, 2, 4, 5]
Aの先頭（7）とBの次（6）を比較 → 6 < 7 なので 6 を取り出す → 結果: [1, 2, 4, 5, 6]
Aに残った 7 を取り出す → 結果: [1, 2, 4, 5, 6, 7]

このように、それぞれの先頭どうしを比較して小さいほうから順に取り出していくだけで、整列されたデータ列を効率よく統合できます。

併合は、大量のデータを分割して個別にソートした後、結果をまとめるといった場面で活用されます。

試験で出るポイント

併合（マージ）は「すでに整列されたデータ列を統合する」処理です。未整列のデータをいきなりマージするのではなく、整列済みのデータが前提であることを押さえておきましょう。

まとめ

この節で学んだ代表的なアルゴリズムを整理します。

分類	アルゴリズム	ポイント
探索	線形探索法	先頭から順に探す。ソート不要。遅い
	2分探索法	真ん中と比較して半分に絞る。ソート必要。速い
整列	バブルソート	隣り合う要素を比較・交換。シンプルだが遅い
	選択ソート	最大値・最小値を選んで端と交換
	クイックソート	ピボットで分割。最も高速
併合	マージ	整列済みデータ列を1つにまとめる