私たちは日常生活でも、「効率よく探す」「早く並べ替える」といった工夫を無意識に行っています。
コンピュータにおいても同様に、問題をどのような手順で解決するかによって、処理にかかる時間や回数が大きく変わります。
この手順を体系的にまとめたものがアルゴリズムです。
本記事では、探索アルゴリズムと整列アルゴリズムを例に、具体的な処理の流れを確認しながら、アルゴリズムの効率性の違いについて理解していきます。
効率性の重要性
情報Ⅰでは、問題解決の過程の中で、効率よく処理する手順を考えることが重要とされています。
コンピュータはこの手順に従って処理を行うため、アルゴリズムの違いによって処理時間や効率が大きく変わります。
同じ問題でも、アルゴリズムによって処理にかかる時間や回数が異なります。
特にデータ量が多い場合、効率の悪いアルゴリズムでは処理に非常に時間がかかるため、効率性が重要になります。
探索アルゴリズムの基礎
探索アルゴリズムとは、データの中から目的の値を見つけるための手順です。
コンピュータは大量のデータの中から特定の情報を探す処理を頻繁に行います。
そのため、どのような方法で探索するかによって、処理の効率が大きく変わります。
探索アルゴリズムにはいくつかの種類がありますが、情報Ⅰでは代表的なものとして次の2つを学びます。
- 線形探索法
- 二分探索法
線形探索法の仕組み
線形探索法は、データを先頭から順番に1つずつ調べていく方法です。
- 先頭から順に比較する
- 見つかるまで繰り返す
- 最後まで見つからない場合もある
二分探索法の仕組み
二分探索法は、データがあらかじめ並んでいる場合に使える方法です。詳細には、データが昇順、又は降順に並んでいる場合に使うことができます。
- 中央の値と比較する
- 探す範囲を半分に絞る
- これを繰り返す
例題で比較する探索効率
例として、昇順に並んだデータ「2、5、8、12、20、25、30」から「20」を探します。
線形探索法の場合
- 2 → 5 → 8 → 12 → 20
- 5回の比較で発見
二分探索法の場合
- 中央（12）と比較 → 大きい
- 右半分（20、25、30）へ
- 中央（25）と比較 → 小さい
- 20を確認 → 発見
→ 3回の比較で発見
このように、二分探索法の方が比較回数が少なく効率的な場合が多いです。
「2」を探す場合には、線形探索法は1回の比較で発見することができるため、探すデータによっては線形探索法のほうが比較回数が少なくなる場合があります。
フローチャートの例を以下に記載します。
整列アルゴリズムの基礎
整列アルゴリズムとは、データを一定の規則に従って並び替えるアルゴリズムのことです。
例えば、整列アルゴリズムでは、小さい順（昇順）や大きい順（降順）にデータを並べ替えます。
整列アルゴリズムには、選択ソート、バブルソート、挿入ソート、マージソート、クイックソートなどがあります。
以下では、一例として選択ソートについて説明します。
選択ソートの仕組み
選択ソートは、未整列部分から最小の値を選び、先頭と交換する方法です。
- 最小値を探す
- 先頭と交換する
- 範囲を狭めて繰り返す
例題で理解する処理の流れ
例として「5、3、8、1」を昇順に並べる場合を考えます。
| 回数 | 配列の状態 | 説明 |
|---|---|---|
| 0回目 | 5、3、8、1 | 初期値 |
| 1回目 | 1、3、8、5 | 最小値1と先頭(5)を交換 |
| 2回目 | 1、3、8、5 | 範囲を狭めて3、8、5の中の最小値を探す。最小値3はそのまま。 |
| 3回目 | 1、3、5、8 | 範囲を狭めて8、5の中の最小値を探す。最小値5と8を交換 |
このように、順番に小さい値を確定していきます。
良いアルゴリズムとは
アルゴリズムの表現や、本記事でアルゴリズムについて学んできました。では、良いアルゴリズムとは、どのようなアルゴリズムなのでしょうか。
コンピュータは、アルゴリズム通りに処理を行います。このため、コンピュータに目的の処理を行わせることができることは大前提です。
その上で、人間にも理解しやすいことが重要です。アルゴリズムを考えた本人だけでなく、他の人も理解できるアルゴリズムでなければ、アルゴリズムの変更や修正などを行いにくいです。
また、本記事で記載したように、コンピュータが効率よく処理を行えるように、アルゴリズムの効率性も意識する必要があります。
実際に学習してわかりにくかったポイント
私が探索や整列のアルゴリズムを学習したとき、最初はそれぞれの手順を覚えることに意識が向いてしまい、「なぜその方法が効率的なのか」までは十分に理解できていませんでした。
特に、線形探索法と二分探索法は名前と手順自体はそれほど難しくありません。しかし、問題を解くときには、それぞれを使える条件まで理解しておく必要があります。
二分探索法は「整列済み」が重要だった
私が最初につまずきやすいと感じたのは、二分探索法です。
「中央の値を調べて、探索範囲を半分にする」という手順自体はすぐに理解できましたが、二分探索法を使うには、データがあらかじめ昇順または降順に並んでいる必要があるという条件は、最初は丸暗記していました。
しかし、実際に並んでいないデータで試してみると理由が分かります。
中央の値より探したい値が大きかったとしても、データがバラバラに並んでいれば「右半分にある」と判断することはできません。そのため、探索範囲を半分に絞ることもできません。
私はここまで理解してから、「二分探索法＝整列済みのデータ」という組み合わせを忘れにくくなりました。
選択ソートは手順を追わないと混乱しやすかった
選択ソートも、説明を読んだだけでは少し分かりにくく感じました。
特に、「最小値を探して交換する」という部分だけ覚えていると、どの範囲から最小値を探すのか分からなくなることがあります。
選択ソートでは、1回処理するたびに先頭側の値が確定していき、次は確定した部分を除いた範囲から最小値を探します。
私は「最小値を探す → 先頭と交換する → 確定した部分を除く」という流れを、実際に数字を書きながら何度か繰り返すことで理解しました。
最初は探索方法の特徴をセットで丸暗記した
定期テストや共通テスト対策としては、最初の段階では次の組み合わせを覚えてしまうのも有効だと思います。
- 線形探索法：先頭から1つずつ調べる
- 二分探索法：中央と比較して範囲を半分にする
- 二分探索法の条件：データが昇順または降順に整列されている
- 選択ソート：未整列部分から最小値を選んで交換する
私は最初にこの程度まで丸暗記し、その後に具体的な数字を使って処理を追うようにしました。
アルゴリズムは文章だけで理解しようとするよりも、実際にデータを書いて、比較する場所や値の移動を1回ずつ追った方が理解しやすい分野だと感じます。
確認問題
【問題1】探索アルゴリズムとは何か。
【問題2】整列アルゴリズムとは何か。
【問題3】次のうち正しいものをすべて選べ。
1.線形探索法は中央の値から探す
2.二分探索法はデータが並んでいなくても使える
3.二分探索法は範囲を半分にしながら探す
4.線形探索法は先頭から順番に調べる
答え：【問題1】データの中から目的の値を見つけるための手順。 【問題2】データを一定の規則に従って並び替えるアルゴリズム。 【問題3】3,4
まとめ
アルゴリズムは問題解決の手順であり、その効率性が重要です。
探索では、線形探索法と二分探索法があり、特に二分探索法は効率的ですが、整列されていることが条件です。
整列では、選択ソートのように手順によって処理の流れが決まります。
問題の状況に応じて適切なアルゴリズムを選ぶことが重要です。