探索アルゴリズム
探索アルゴリズムとは、以下のようなデータの列から欲しいデータをさがすアルゴリズムです。
| インデックス | 0 | 1 | 2 | … | n |
|---|---|---|---|---|---|
| データ | d0 | d1 | d2 | … | dn |
探索アルゴリズムには、いくつか種類があります。
この中から、メジャーな線形探索と二分探索についてみてみましょう。
線形探索
一番簡単な探索方法です。
データの先頭d0から、順番に末尾dnまでインデックスを1つずつ増やしながら、目的のデータと一致するかどうか調べます。
二分探索
二分木を使った探索方法です。
この探索方法を使う時は、データが昇順、または降順にソートされていることが前提となります。
二分探索では、範囲の真ん中のデータと目的のデータを比べて、探索する範囲をどんどん狭めていきます。
実際に昇順でソート済みのデータ列から2を探してみましょう。
| 2 | 4 | 5 | 8 | 9 | 10 | 22 |
|---|
二分探索では、まず調べる範囲の中央の値に注目します。
ここでは、中央値として8に注目します。
目的のデータ2は8よりも小さいので、2があるとすれば8よりも左側だと考えられます。
そこで、探索範囲を8より左のデータ列に狭めます。
| 2 | 4 | 5 |
|---|
また、この範囲での中央値4と目的のデータを比べます。
2の方が小さいので、このデータ列に2があるとすれば、4より左側ですね。
更に、左側に範囲を狭めましょう。
| 2 |
|---|
この範囲の中央値は2です。
目的のデータ2と比べると、一致します。
このデータ列から目的のデータ2を見つけることができました。
ソートアルゴリズム
ソートアルゴリズムとは、データ列を昇順、または降順に並び替えるアルゴリズムです。
今回は、有名なバブルソートと選択ソートを見ていきます。
バブルソート
バブルソートでは、隣り合う要素の大小を比較して、入れ替える操作を繰り返すことでデータ列を並び替えます。
実際に次のデータ列を昇順にソートしてみます。
| 5 | 4 | 3 |
|---|
まず先頭のデータ5と2番目のデータ3を比べます。5の方が大きいので、5と3を入れ変えます。
| 4 | 5 | 3 |
|---|
次に、2番目の要素と3番目の要素を比較します。
2番目の要素5の方が大きいので、5と4を入れ替えます。
| 4 | 3 | 5 |
|---|
末尾の要素との比較が終わると、末尾に一番大きい数字が表れます。
よって末尾はこれで固定します。
末尾の要素をソートの範囲から外します。
| 4 | 3 |
|---|
末尾を外したデータ列で、一番値の大きいデータを同様の処理を繰り返してこの範囲の末尾に移動させます。
| 3 | 4 |
|---|
これを繰り返すことで、データ列を昇順に並び替えることができます。
| 3 | 4 | 5 |
|---|
選択ソート
昇順の選択ソートでは、先頭より小さい要素を見つけるたびにその要素と先頭の要素を入れ替えることで、並び替えます。
実際に次のデータ列を昇順にソートしてみます。
| 5 | 4 | 3 |
|---|
まず、先頭の要素5と2番目の要素4を比べます。
4の方が小さいので、データを入れ替えます。
| 4 | 5 | 3 |
|---|
次に現在の先頭の要素4と3番目の要素3を比べます。
3の方が小さいので、データを入れ替えます。
| 3 | 5 | 4 |
|---|
末尾までチェックしたら、先頭にはデータ列の中で1番小さい要素がはいっています。
そのため、ソートする範囲から先頭を取り除きます。
| 5 | 4 |
|---|
同様の処理を狭めた範囲でも繰り返すことで、最終的にデータ列を昇順に並び替えることができます。
| 3 | 4 | 5 |
|---|