頭の体操・バブルソート

2012.06.07

こんばんは、アーキテクトの小山です。
仕事で疲れた時はアルゴリズムを作って頭の体操をしています。

今回は仕組みが簡単なバブルソートのアルゴリズムをphpで作ってみます。

そもそも、バブルソートとは何ぞやという方に簡単に説明すると、
全ての要素に関して、隣接する要素と比較し順序が逆であれば入れ替える。(wikipediaより抜粋)
ということです。
一つ目と二つ目を比べて小さい順に並べ直す

二つ目と三つ目を比べて小さい順に並べ直す、

全てが小さい順になるまで繰り返す

という感じの流れになります。

お時間のある方は実際にコードを打って考えてみてください。

頭で考えると簡単そうに見えても、シンプルに書くには意外と大変です。
大体以下のとおりになると思います。

$hoge = array(9,4,8,6,4,3,5,1,7,2,0);
$max = count($hoge);

for($i = 0; $i < $max; $i++){
for($f = $max-1; $f > $i; $f–){
if($hoge[$f - 1] > $hoge[$f]){
$temp = $hoge[$f];
$hoge[$f] = $hoge[$f - 1];
$hoge[$f - 1] = $temp;
$temp = null;
}
}
}

var_dump($hoge);

要素の数($max)だけループ、その間$をインクリメント。
$hoge-1を最大値とし、$fが$iより大きくなるまでデクリメントを繰り返す。
その中で隣の要素を比較し、入れ替える。

値の入れ替えのためには最初の数字を格納する変数の他に、一時的に値を保持する変数が必要です(例だと$temp)。
一回$tempを使用したら変数をリセットしたいのでnullを入れました。これはなんとなく気持ち悪いので入れただけですが。

如何でしたでしょうか?無事にソートをすることが出来ましたか?

FizzBuzz問題や、3の数だけアホになる問題等も頭の体操になりますので、
プロジェクトが煮詰まったときはプログラミングするのもいいかもしれません。

lab-php5

一覧へ