【真面目版】アルゴリズムってなに？整列・探索・再帰をやさしく解説

はじめに

この記事では、プログラミングの世界で特に重要な 3 つのアルゴリズムのジャンルを、日常のたとえ話を使いながら紹介します。

---

1. 整列アルゴリズム ── 「並べ替え」の技術

そもそも「整列」って？

整列（ソート）とは、バラバラのデータを小さい順や大きい順に並べ替えることです。

たとえば、テストの答案用紙を出席番号順に並べ直す作業を想像してください。手元に 30 枚の答案があるとき、あなたはどうやって並べますか？ 実は、その「やり方」こそがアルゴリズムなのです。

代表的な整列アルゴリズム

バブルソート ── 隣どうしを比べてコツコツ入れ替え

お風呂の泡（バブル）が水面にぽこぽこ浮かんでいくイメージです。

• 隣り合った 2 つの数を比べる
• 左が大きければ入れ替える
• これを端から端まで何度も繰り返す

たとえ話： 背の順に並ぶとき、隣の人と背を比べて「自分の方が高ければ後ろへ」を繰り返す方法です。シンプルですが、人数が多いと時間がかかります。

選択ソート ── 一番小さいものを探してから並べる

• 全体を見渡して一番小さい数を見つける
• それを先頭に置く
• 残りの中でまた一番小さいものを探す……を繰り返す

たとえ話： トランプの手札を並べるとき、まず一番小さいカードを探して左端に置き、次に小さいカードを探して……とやるイメージです。

クイックソート ── 基準を決めて左右に振り分け

• 1 つの数を「基準（ピボット）」として選ぶ
• 基準より小さいグループと大きいグループに分ける
• それぞれのグループの中でまた同じことをする

たとえ話： 本棚の本を「あ行〜な行」と「は行〜わ行」に分けてから、それぞれの中をさらに細かく分けていく片づけ方です。実際のプログラムでもっとも使われるソートのひとつで、非常に高速です。

どれを使えばいいの？

アルゴリズム	わかりやすさ	スピード（大量データ）
バブルソート	とても簡単	遅い
選択ソート	簡単	やや遅い
クイックソート	やや複雑	とても速い

データが少ないうちはどれでも大差ありませんが、何万件、何百万件になるとクイックソートのような高速な方法が必要になります。

---

2. 探索アルゴリズム ── 「探しもの」の技術

そもそも「探索」って？

たくさんのデータの中から、目的のデータを見つけ出すことです。図書館で 1 冊の本を探すとき、あなたはどうしますか？

代表的な探索アルゴリズム

線形探索（リニアサーチ） ── 端から順番に見る

• データの先頭から 1 つずつ順番に確認する
• 目的のデータが見つかったらそこで終了

たとえ話： 本棚の左端から 1 冊ずつ「これかな？ これかな？」と確認していく方法です。確実ですが、本が 1 万冊あったら大変です。

二分探索（バイナリサーチ） ── 半分に絞って効率よく

• データがあらかじめ順番に並んでいることが前提
• 真ん中のデータを見て、目的の値より大きいか小さいかを判定する
• 半分を切り捨てて、残った半分でまた真ん中を見る

たとえ話： 辞書で「ねこ」を引くとき、辞書のちょうど真ん中あたりを開いて「は行だから、もっと前だ」と半分を捨て、残りの真ん中を開いて……と繰り返す方法です。1 万ページの辞書でも、わずか 14 回ほどの比較で目的のページにたどり着けます。

効率の違いを実感しよう

100 万件のデータから 1 つを探す場合を考えてみましょう。

• 線形探索： 最悪 100 万回の比較が必要
• 二分探索： たった約 20 回の比較で見つかる

この差は、データが増えるほど劇的に広がります。ただし二分探索には「データがすでに並んでいる」という条件があるため、事前にソートが必要です。ここで整列アルゴリズムが活躍するわけですね。

---

3. 再帰的アルゴリズム ── 「自分自身を呼ぶ」技術

そもそも「再帰」って？

再帰（さいき）とは、ある手順の中で「自分自身をもう一度使う」テクニックです。合わせ鏡のように、鏡の中にまた鏡が映っている……そんなイメージです。

身近な例で理解する

例 1：階段の段数を数える

あなたは長い階段の途中に立っています。「ここは何段目？」と知りたいとき、こんな方法が取れます。

1. 一段下の人に「あなたは何段目？」と聞く
2. その人もまた一段下の人に同じ質問をする
3. 一番下の人は「1 段目だよ」と答える
4. その答えに 1 を足して上に返していく

これが再帰です。「自分の問題を、少し小さくした同じ問題に置き換えて解く」のが特徴です。

例 2：ロシアのマトリョーシカ人形

大きな人形を開けると中に小さな人形があり、それを開けるとさらに小さな人形が出てくる。一番小さな人形（これ以上開けられない）にたどり着いたら終わりです。

• 再帰のポイント： 大きな問題を「同じ形のより小さな問題」に分解する
• 終了条件（ベースケース）： これ以上分解しなくていい最小の状態

再帰がないとどうなる？

再帰を使わずに書けるプログラムもありますが、問題によっては再帰なしだと手順がとても複雑になります。たとえば、フォルダの中のフォルダの中のフォルダ……をすべて調べる処理は、再帰を使えば「フォルダを開ける → 中にフォルダがあればまた同じ処理をする」とシンプルに書けます。

再帰の注意点

再帰にはひとつ大事なルールがあります。それは「必ず終わる条件を用意する」ことです。終了条件がないと、永遠に自分自身を呼び続けて、コンピュータがフリーズしてしまいます。合わせ鏡が無限に続くのは美しいですが、プログラムでは困りものです。

---

3 つのアルゴリズムのつながり

先ほど紹介したクイックソートは、「基準を決めて分けて、それぞれの中でまた同じことをする」という再帰的なアルゴリズムです。そして、高速な二分探索を使うためには、データがソートされている必要があります。つまり、整列→探索の順でアルゴリズムが協力し合い、再帰という考え方がその土台を支えているのです。

---

まとめ

ジャンル	ひとことで言うと	日常のたとえ
整列（ソート）	データを順番に並べる	テストの答案を出席番号順に並べ替える
探索（サーチ）	目的のデータを見つける	辞書でことばを引く
再帰	同じ手順を小さくして繰り返す	マトリョーシカ人形を順番に開ける