アルゴリズムの導入の導入
みなさん、”アルゴリズム“と聞いて何を思い浮かべますか？
なんとなく名前は知っているけど具体的に内容は説明できない、という方は案外多いのではないかと思います。(ちなみに、某体操は一切アルゴリズムではありません。)
アルゴリズムは、”問題解決の手順を定式化したもの”と定義されています。
言葉で説明されてもいまいちイメージしにくいですね。
ソートのアルゴリズム
アルゴリズムの話をするときに、よく取り上げられるものがソートに関するアルゴリズムです。
つまり、”どんな順番でどんな要素数の配列を投じられても正しく整列させて返すもの”、がソートのアルゴリズムとなります。
ソートのアルゴリズムで一番わかりやすいのが挿入ソート(INSERT SORT)と呼ばれるものです。
今回はPHPで実装してみます。
アルゴリズムを実装すると聞くと身構えてしまう人もいるかもしれませんが、実際にやってみると大して難しくはありません。
<?php
function insert_sort($array = []){
// 渡された配列の要素数を取得する
$size = count($array);
// 最初に渡された配列の要素を一つ一つ見ていく
for ($i = 1; $i < $size; $i++){
// i番目の要素を一時的に変数に詰める
$tmp = $array[$i];
// $tmpを配列に詰め直す位置を探す
for ($j = $i - 1; $j >= 0 && $array[$j] > $tmp ; $j--){
$array[$j + 1] = $array[$j];
}
$array[$j + 1] = $tmp;
}
return $array;
}
$test_array1 = array(7,1,5,2,6,3,4,8);
var_dump(insert_sort($test_array));
$test_array2 = array(100,23,42,14,67,88,32,55,62,41,33,68);
var_dump(insert_sort($test_array2));
insert_sortという関数の中身が挿入ソートになります。
比較的、理屈の流れは追いやすいかと思いますが、関数に渡された配列の要素を一つ一つ比較し、改めてソート通りに配列に詰め直しています。最後の要素まで正しい位置に詰めたら配列全体がソートされていることになります。
コードの最後に要素も要素数も違う配列を二つ用意していますが、上のファイルを実行すれば確認できますが両方とも正しくソートされています。
つまり、どのような配列を渡しても同じ処理で正しい結果を返せているので、insert_sortという関数はアルゴリズムであると言えます。
アルゴリズムの評価
今回は例として挿入ソートを用いましたが、ソートに関するアルゴリズムは色々なものが存在します。
アルゴリズムの優劣を決めるのは、その計算効率です。
簡単に言うと、無駄な計算や手順が多ければ多いほどそのアルゴリズムの効率は悪いですし、無駄なく答えを導き出せるほど良いアルゴリズムと言えます。
とはいえ、上記のようなソートのアルゴリズムであれば最初に渡される配列の並びによって計算手順の数は大いに変わりますし、一番時間がかからない場合を考えるのか、もしくは一番時間がかかる場合を考えるかによっても評価は大きく変わります。
どういう条件で用いるかによってアルゴリズムの取捨選択は決まるといえます。
ちなみに、まず間違いなく効率最悪と言われるアルゴリズムにボゴソートというものがあります。これは、配列を渡されたときランダムにシャッフルし、その結果が正しいソート結果と一致していればその配列を返し、一致していなければもう一度シャッフルする、というのを偶然によって正しくソートされるまで繰り返すアルゴリズムです。
一切覚えなくていいです。
おまけ
今回はソートを例にアルゴリズムの説明をしましたが、ただ単にソートするだけなら
<?php
$test_array1 = array(7,1,5,2,6,3,4,8);
sort($test_array1);
で完了します。
残酷ですね。
