第４回 分布数え上げソート

最速とされているクイックソートの計算量は ですが、分布数え上げソートは です。その速さはクイックソートを上回ります。

<?php

function counting_sort($array, $min, $max)
{
  // 値の出現回数を数え上げる。
  $count_list = array();
  foreach ($array as $i) {
    if (isset($count_list[$i])) {
      $count_list[$i]++;
    } else {
      $count_list[$i] = 1;
    }
  }

  // 出現回数だけ出力をすれば並べ替えたことと同じになる
  $ret = array();
  for ($key = $min; $key <= $max; $key++) {
    if (isset($count_list[$key])) {
      for($n = 0; $n < $count_list[$key]; $n++) {
        $ret[] = $key;
      }
    }
  }

  return $ret;
}

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

実行結果はこうなります。

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

結果としてソートされていますが、値の入れ替えを行っていないのが計算量 を実現するポイントです。ループを２回回しているだけなので、計算回数はデータ数×２回で済んでいます。
これができるのは、値のminとmaxがわかっているからになります。クイックソートは値の上限下限を気にしませんが、分布数え上げソートは出力するときに「小さい方から出力」というのを実現するために下限から上限へのforループを回しています。
「上限下限が事前にわかっている」という制約条件を生かすことでより速くなっているということです。現実にも「テストの点数は0〜100点」など、事前にわかっていることは多いと思います。

個人的には一番好きなアルゴリズムです。特にPHPとの相性がよく、実際に応用を使用することもあります。ソート実装としては反則ですが、ksort()を使うと制約条件なしで使えます。

<?php

function counting_sort_kai($array)
{
  // 値の出現回数を数え上げる。
  $count_list = array();
  foreach ($array as $i) {
    if (isset($count_list[$i])) {
      $count_list[$i]++;
    } else {
      $count_list[$i] = 1;
    }
  }

  // 出現回数だけ出力をすれば並べ替えたことと同じになる
  $ret = array();
  ksort($count_list);
  foreach ($count_list as $key => $val) {
    for($n = 0; $n < $val; $n++) {
      $ret[] = $key;
    }
  }

  return $ret;
}

これが何に使えるかというと、例えば「UserAgentを数え上げてソートしてCSV出力する」という作業がある場合です。

• ksort()ではなくrsort()を使う
• forループを回して$retを作る代わりにcsv１行をechoする

に作り変えればすぐできます。配列（連想配列）のキーには文字列を使えるので、出現回数のカウントにはもってこいです。

基本のアルゴリズムは直接使うことはありませんが、応用がいろいろあります。基本があってはじめて応用があるものです。
次は同じく配列を使ったアルゴリズムである「エラトステネスのふるい」です。