私たちは日常生活でも、「効率よく探す」「早く並べ替える」といった工夫を無意識に行っています。
コンピュータにおいても同様に、問題をどのような手順で解決するかによって、処理にかかる時間や回数が大きく変わります。
この手順を体系的にまとめたものがアルゴリズムです。
本記事では、探索アルゴリズムと整列アルゴリズムを例に、具体的な処理の流れを確認しながら、アルゴリズムの効率性の違いについて理解していきます。
効率性の重要性
情報Ⅰでは、問題解決の過程の中で、効率よく処理する手順を考えることが重要とされています。
コンピュータはこの手順に従って処理を行うため、アルゴリズムの違いによって処理時間や効率が大きく変わります。
同じ問題でも、アルゴリズムによって処理にかかる時間や回数が異なります。
特にデータ量が多い場合、効率の悪いアルゴリズムでは処理に非常に時間がかかるため、効率性が重要になります。
探索アルゴリズムの基礎
探索アルゴリズムとは、データの中から目的の値を見つけるための手順です。
コンピュータは大量のデータの中から特定の情報を探す処理を頻繁に行います。
そのため、どのような方法で探索するかによって、処理の効率が大きく変わります。
探索アルゴリズムにはいくつかの種類がありますが、情報Ⅰでは代表的なものとして次の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】探索アルゴリズムとは何か。
【問題2】整列アルゴリズムとは何か。
【問題3】次のうち正しいものをすべて選べ。
1.線形探索法は中央の値から探す
2.二分探索法はデータが並んでいなくても使える
3.二分探索法は範囲を半分にしながら探す
4.線形探索法は先頭から順番に調べる
答え：【問題1】データの中から目的の値を見つけるための手順。 【問題2】データを一定の規則に従って並び替えるアルゴリズム。 【問題3】3,4
まとめ
アルゴリズムは問題解決の手順であり、その効率性が重要です。
探索では、線形探索法と二分探索法があり、特に二分探索法は効率的ですが、整列されていることが条件です。
整列では、選択ソートのように手順によって処理の流れが決まります。
問題の状況に応じて適切なアルゴリズムを選ぶことが重要です。