第１回 バブルソート

10番煎じぐらいな気がしなくもないですが、PHPでアルゴリズムのお勉強です。
初回はおなじみバブルソート。バブルソートそのものの解説はwikipediaでどうぞ。

<?php

function bubble_sort(&$array)
{
  $count = count($array);
  for ($n = $count - 1; $n > 0; $n--) {    // $n はソート対象範囲の最大
    for ($i = 0; $i < $n; $i++) {          // $i はソートのポインタ
      // ポインタの数値がポインタ右側より大きければ入れ替える。
      if ($array[$i] > $array[$i+1]) {
        $temp = $array[$i];
        $array[$i]   = $array[$i+1];
        $array[$i+1] = $temp;
      }
    }
    echo join(', ', $array) . "\n";
  }
}

$input = array(5, 2, 4, 3, 4, 8, 7, 2, 1);
echo '処理前：' . join(', ', $input) . "\n";
echo "処理中...\n";
bubble_sort($input);
echo '処理後：' . join(', ', $input) . "\n";

出力結果は以下。

処理前：5, 2, 4, 3, 4, 8, 7, 2, 1
処理中...
2, 4, 3, 4, 5, 7, 2, 1, 8
2, 3, 4, 4, 5, 2, 1, 7, 8
2, 3, 4, 4, 2, 1, 5, 7, 8
2, 3, 4, 2, 1, 4, 5, 7, 8
2, 3, 2, 1, 4, 4, 5, 7, 8
2, 2, 1, 3, 4, 4, 5, 7, 8
2, 1, 2, 3, 4, 4, 5, 7, 8
1, 2, 2, 3, 4, 4, 5, 7, 8
処理後：1, 2, 2, 3, 4, 4, 5, 7, 8

一番単純なソートアルゴリズムですが、実際にはこれではなく「クイックソート」が使われることが多いです。PHPのsort()関数もクイックソートで実装されています。というわけで次回はクイックソートです。