第２回 クイックソート

クイックソートはPHPに限らずいろんな言語でライブラリとして実装されており、例えばC言語ではqsort()として標準ライブラリとして用意されています。
その名の通り「速いソート」で、実装時の工夫等もあり汎用ソートアルゴリズムとしては最速とされています。
解説はやっぱりwikipediaにおまかせとして、そのgifアニメで表示されている方法で実装してみます。

<?php

function quick_sort(&$array)
{
  _qsort($array, 0, count($array) - 1);
}

function _qsort(&$array, $start, $end)
{
  // ソート対象が１個以下なら何もしない
  if ($start >= $end) {
    return;
  }
  
  $lt = $start;       // 左端のポインタ
  $ge = $end - 1;     // 右端のポインタ
  $pivot = $array[$end];    // 基準値
  
  // ポインタがクロスするまでループを回す
  while ($lt < $ge) {
    // 左端のポインタが右端にくるまで右に移動させる。
    // 基準値以上の値が現れたらそこでストップ。
    while ($lt < $end) {
      if ($array[$lt] >= $pivot) {
        break;
      }
      $lt++;
    }
    
    // 右端のポインタが左端にくるまで左に移動させる。
    // 基準値より小さい値が現れたらそこでストップ。
    while ($ge > $start) {
      if ($array[$ge] < $pivot) {
        break;
      }
      $ge--;
    }
    
    // ポインタがクロスしていなければ、値を入れ替える（値の小さいものを左へ、大きいものを右へ移動させる）
    if ($lt < $ge) {
      $temp = $array[$lt];
      $array[$lt] = $array[$ge];
      $array[$ge] = $temp;
      $lt++;
      $ge--;
    }
  }
  
  // 一番右にある基準値を真ん中へ移動させる
  $array[$end] = $array[$lt];
  $array[$lt]  = $pivot;
  
  echo join(', ', array_slice($array, $start, $end - $start + 1)) . " (pivot: $pivot)\n";
  
  // 基準値より小さいグループに対してさらにソートする。
  // 基準値より大きいグループに対してさらにソートする。
  // グループ内の値が１個以下になっていれば呼び出した先で処理は終了する（１個以下＝常にソート済み）
  _qsort($array, $start, $lt - 1);
  _qsort($array, $lt + 1, $end);  
}

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

出力結果は以下。

処理前：5, 2, 4, 3, 4, 8, 7, 2, 1, 6
処理中...
5, 2, 4, 3, 4, 1, 2, 6, 8, 7 (pivot: 6)
1, 2, 4, 3, 4, 5, 2 (pivot: 2)
2, 3, 4, 5, 4 (pivot: 2)
3, 4, 5, 4 (pivot: 4)
4, 5 (pivot: 4)
7, 8 (pivot: 7)
処理後：1, 2, 2, 3, 4, 4, 5, 6, 7, 8

やっていることは「基準値より小さい値を左側に、大きい値を右側に移動させる」ということです。そして、その小さい値のグループに対して再度同じことを、大きい値のグループにも再度同じことをしてやる。そうするうちに最終的にすべてがソートされていきます。
_qsort()の中でさらに_qsort()を呼び出していますが、これを「再帰呼び出し」といいます。再帰について理解できるかどうかがアルゴリズムの勉強の成否を分けますので、がんばって咀嚼してみてください。以下にソート処理中の出力を整理したものを用意しておきます。

5, 2, 4, 3, 4, 1, 2, 6, 8, 7
1, 2, 4, 3, 4, 5, 2, 6, 7, 8
1, 2, 2, 3, 4, 5, 4, 6, 7, 8
1, 2, 2, 3, 4, 5, 4, 6, 7, 8
1, 2, 2, 3, 4, 4, 5, 6, 7, 8

次回はバブルソートとクイックソートを比較しながら「計算量」の話です。