クイックソートのイメージ
前回に引き続き、またソートアルゴリズムをPHPで作成しました。
出来ないと次にいけない性格なので、ずいぶんと前より時間がかかりました。
その間に、あれもこれも書きたいと思ったけど、全部忘れました。
でもこれ書けたのでスッキリします！
今回のソートは、適当に選んだ数字を、小さい|pivot|大きいに分別していきます。
適当に選んだ数字の事をpivotというらしいです。
何でそう思ったかっていうとpivotって変数でよく定義されてるからです。
pivotは配列の中に入ってる数字なら何でも良いです。
pivotには中央値を毎回指定するとプログラム実行速度が早くなる場合があるそうです。
だから中央値を取るのが望ましいそうですよ！
INDEX
準備
配列などをして、クイックソートに必要なパラメータを準備します。
クイックソートは再帰を利用して行うのが一般的らしいので、
作っとくと色々便利なクラスを用意します。
$ar = array(10,65,8,56,32,5,5,89,3,121,1);
class SortQuick
{
}
コンストラクタ定義
クイックソートに必要な、データを受け取る為に
construtメソッドを作ります。
結果を参照させるメンバ変数を作ります。
public $result = array();
function __construct($data)
{
$arcount = count($data);
$R = $arcount-1;
$L = 0;
$this->Main($data,$L,$R);
//$this->output($this->result);
}
参照渡しする
とりあえずメインの処理をするメソッドを用意します。
この元の配列は参照で渡さないと、データが変わって行かないので、
参照で渡す事にします。
private function main(&$data,$L,$R)
こうなります。
クラスならメンバ変数使っても良いと思います。
pivotの選定
適当に選んだ数字pivotには左端の数字を入れておきます。
pivotの選び方について良い教材を見つけることが出来なかったので
左端の数字を入れました。
private function main(&$data,$L,$R)
{
$pivot = $data[$L];
}
一番良いのは配列の中の数値の平均値に近い番号が入っている
配列の番号取って来るのが良いのでしょうか。わかんないです！
配列の右端と左端を取る
さて配列の中には
[10,65,8,56,32,5,5,89,3,121,1]
この数字が入っております。
private function main(&$data,$L,$R)
{
$pivot = $data[$L];
$i=$L;
$j=$R;
}
ここでは、$iと$jという二つの変数に
左端の配列番号と右端の配列番号を入れます。
これを、左側はpivotより多ければ加算し
右側はpivotより少なければ減算していきます。
メインのプログラム
forでも試しましたがなんか上手く行かなかったので
元のサンプル通り勝手に回り続けるループ使いました。
private function main(&$data,$L,$R)
{
$pivot = $data[$L];
$i=$L;
$j=$R;
while(1)
{
while($data[$i]<$pivot) { $i++; }
while($data[$j]>$pivot) { $j--; }
if($i>=$j){
$this->result = $data;
break;
};
$tmp = $data[$i];
$data[$i] = $data[$j];
$data[$j] = $tmp;
$i++; //配列の左端から見るから上がる
$j--; //配列の右端から見るから下がる
}
}
左側の配列番号の値が右側の配列番号の値以上になった場合に、
このループはおしまいになります。
おしまいにならない場合は、配列番号iと配列番号jの入れ替えが行われ
配列番号iが1個増えて、配列番号jが一個減ります。
再帰処理
再帰とはあるプログラムの中からまた同じプログラムを呼び出すという発想です。
詳しく知りたい人は、再帰のWikipedia見てからハノイの塔のGifアニメとにらめっこしてくれればいいと思います。
この場合だと、このmainというメソッドの中から、同じmainというメソッドを呼び出します。
先ほどの入れ替え処理によって、ソートが確定した配列の番号があります。
なので、右と左それぞれ、確定した配列の番号を避けて、決めた条件まで
同じ関数を使い続けます。
private function main(&$data,$L,$R)
{
$pivot = $data[$L];
$i=$L;
$j=$R;
・・・・
if($i-1>$L)
{
//配列と今回の左端の数と今回の左端からの距離-1をパラメータにする
$this->main($data,$L,$i-1);
}
if($j+1<$R)
{
//配列と今回の右端からの距離-1と今回の右端の数をパラメータにする
$this->main($data,$j+1,$R);
}
}
そうすることで、小さいもん順に数字がならびます。
コード全文
今回のコードです。
アルゴリズム一個覚えるのってしんどいですね。
もっと数学勉強しておけばよかった。
社会に出てから使わないじゃんってことは
ないんじゃないかなーって思いました。
そう思う頃には、時既に遅しなんですよね。
とゆーわけで、今回はこんな感じで書きました。
読んでくれた人ありがとうございました。
$ar = array();
for($i=0; $i<1000; $i++)
{
$ar[] = rand(1,1000);
}
$quick = new SortQuick($ar);
class SortQuick
{
public $result = array();
function __construct($data)
{
$arcount = count($data);
$R = $arcount-1;
$L = 0;
$this->Main($data,$L,$R);
//$this->output($this->result); 訂正 5/27
}
private function main(&$data,$L,$R)
{
$pivot = $data[$L];
$i=$L;
$j=$R;
while(1)
{
while($data[$i]<$pivot) { $i++; }
while($data[$j]>$pivot) { $j--; }
if($i>=$j){
$this->result = $data;
break;
};
$tmp = $data[$i];
$data[$i] = $data[$j];
$data[$j] = $tmp;
$i++;
$j--;
}
if($i-1>$L)
{
$this->main($data,$L,$i-1);
}
if($j+1<$R)
{
$this->main($data,$j+1,$R);
}
}
/* 訂正 5/27
private function output($o)
{
echo "<pre>";
print_r($o);
echo "</pre>";
}
*/
}
echo "<pre>";
var_dump($quick->result);
echo "</pre>";
とりあえず動きました。
