メシのタネ

Webプログラミング 備忘録

  • DOMをPHPで操作できたらいいよね

    そうだよね。そう思うよね。JavaScriptでやると、画面がガタついたりするもんね。そうならないようにする方法もあるかもしれないけど、僕はできませんので、サーバー側でなんとかできたらええなぁと思って挑戦したけど、できませんでしたよ。PHP標準でHTMLをDOMにできるらしい今、技[...]

    続きを読む
  • 設計書ってなんで書くの?

    設計書をなぜ書くのかから始めてかれこれ3年近くこの禅問答をやっているわけですが、いまだに答えは出ません。ただ、その禅問答をやる中で設計書に対する取り組み方は大きく変わったので、その一部でも書いていきたい。基本設計はとにもかくにも必要だと思う設計書はいらぬ!という話をよく聞くし、自分[...]

    続きを読む
  • 書ききってやる。

    久々に書いてみる。久々に文章を書くということをやってみようと思う。伝える作業を観察したいと思ったからそうしたいと考えた。情緒的な文章は基本的にゴミ箱にぽいしてきましたが、情緒的なのも自分だと思う。「文章をかくという作業は、とりもなおさず自分と自分をとりまく事物との距離を確認すること[...]

    続きを読む
  • 普通の会社で2年普通に働いて思う事

    えらい寒くなりました。文句言いながらも現職を続けて2017年12月1日にめでたく2年がたちました。分かりやすいが乱暴に言えばITドカタと呼ばれる業界に入って案件のヒエラルキーの無慈悲さを痛感しながらも、それでもしょうがないと頑張る人たちに心を打たれながら「じゃあ俺も」と頑張れない自分に挫折して、とあ[...]

    続きを読む
  • jQueryUiのDatepicker利用時にminDate設定するとバグる件

    題名の通りなんですが、DatepickerでminDate使うとバグります。また後でキャプチャ見て貰いますけど、灰色の部分が、minDateで設定した日付が反復して出るようになるんですね。こういうの気が付かない人がいるかも知れませんが、ChoromeでminDate設定してる人は気にしてみてくだ[...]

    続きを読む

PHPでクイックソートをやってみた

バイク

クイックソートのイメージ

前回に引き続き、またソートアルゴリズムをPHPで作成しました。
出来ないと次にいけない性格なので、ずいぶんと前より時間がかかりました。
その間に、あれもこれも書きたいと思ったけど、全部忘れました。
でもこれ書けたのでスッキリします!

今回のソートは、適当に選んだ数字を、小さい|pivot|大きいに分別していきます。
適当に選んだ数字の事をpivotというらしいです。
何でそう思ったかっていうとpivotって変数でよく定義されてるからです。
pivotは配列の中に入ってる数字なら何でも良いです。
pivotには中央値を毎回指定するとプログラム実行速度が早くなる場合があるそうです。
だから中央値を取るのが望ましいそうですよ!

準備

配列などをして、クイックソートに必要なパラメータを準備します。
クイックソートは再帰を利用して行うのが一般的らしいので、
作っとくと色々便利なクラスを用意します。

<br />
$ar = array(10,65,8,56,32,5,5,89,3,121,1);</p>
<p>class SortQuick<br />
{</p>
<p>}</p>
<p>

コンストラクタ定義

クイックソートに必要な、データを受け取る為に
construtメソッドを作ります。
結果を参照させるメンバ変数を作ります。

<br />
     public $result = array();</p>
<p>     function __construct($data)<br />
     {<br />
          $arcount = count($data);<br />
          $R = $arcount-1;<br />
          $L = 0;<br />
          $this-&gt;Main($data,$L,$R);<br />
          //$this-&gt;output($this-&gt;result);<br />
     }</p>
<p>

参照渡しする

とりあえずメインの処理をするメソッドを用意します。
この元の配列は参照で渡さないと、データが変わって行かないので、
参照で渡す事にします。

<br />
 private function main(&amp;$data,$L,$R)<br />

こうなります。
クラスならメンバ変数使っても良いと思います。

pivotの選定

適当に選んだ数字pivotには左端の数字を入れておきます。
pivotの選び方について良い教材を見つけることが出来なかったので
左端の数字を入れました。

<br />
     private function main(&amp;$data,$L,$R)<br />
     {</p>
<p>          $pivot = $data[$L];</p>
<p>     }</p>
<p>

一番良いのは配列の中の数値の平均値に近い番号が入っている
配列の番号取って来るのが良いのでしょうか。わかんないです!

配列の右端と左端を取る

さて配列の中には
[10,65,8,56,32,5,5,89,3,121,1]
この数字が入っております。

<br />
     private function main(&amp;$data,$L,$R)<br />
     {</p>
<p>          $pivot = $data[$L];<br />
          $i=$L;<br />
          $j=$R;<br />
     }</p>
<p>

ここでは、$iと$jという二つの変数に
左端の配列番号と右端の配列番号を入れます。

これを、左側はpivotより多ければ加算し
右側はpivotより少なければ減算していきます。

メインのプログラム

forでも試しましたがなんか上手く行かなかったので
元のサンプル通り勝手に回り続けるループ使いました。

<br />
     private function main(&amp;$data,$L,$R)<br />
     {</p>
<p>          $pivot = $data[$L];</p>
<p>          $i=$L;<br />
          $j=$R;</p>
<p>          while(1)<br />
          {<br />
               while($data[$i]&lt;$pivot) { $i++; }<br />
               while($data[$j]&gt;$pivot) { $j--; }<br />
               if($i&gt;=$j){<br />
                    $this-&gt;result = $data;<br />
                    break;<br />
               };</p>
<p>               $tmp = $data[$i];<br />
               $data[$i] = $data[$j];<br />
               $data[$j] = $tmp;</p>
<p>               $i++; //配列の左端から見るから上がる<br />
               $j--; //配列の右端から見るから下がる<br />
          }</p>
<p>     }</p>
<p>

左側の配列番号の値が右側の配列番号の値以上になった場合に、
このループはおしまいになります。
おしまいにならない場合は、配列番号iと配列番号jの入れ替えが行われ
配列番号iが1個増えて、配列番号jが一個減ります。

再帰処理

再帰とはあるプログラムの中からまた同じプログラムを呼び出すという発想です。
詳しく知りたい人は、再帰のWikipedia見てからハノイの塔のGifアニメとにらめっこしてくれればいいと思います。
この場合だと、このmainというメソッドの中から、同じmainというメソッドを呼び出します。

先ほどの入れ替え処理によって、ソートが確定した配列の番号があります。
なので、右と左それぞれ、確定した配列の番号を避けて、決めた条件まで
同じ関数を使い続けます。

<br />
     private function main(&amp;$data,$L,$R)<br />
     {</p>
<p>          $pivot = $data[$L];</p>
<p>          $i=$L;<br />
          $j=$R;</p>
<p>          ・・・・</p>
<p>          if($i-1&gt;$L)<br />
          {<br />
               //配列と今回の左端の数と今回の左端からの距離-1をパラメータにする<br />
               $this-&gt;main($data,$L,$i-1);<br />
          }</p>
<p>          if($j+1&lt;$R)<br />
          {<br />
               //配列と今回の右端からの距離-1と今回の右端の数をパラメータにする<br />
               $this-&gt;main($data,$j+1,$R);<br />
          }          </p>
<p>     }</p>
<p>

そうすることで、小さいもん順に数字がならびます。

コード全文

今回のコードです。
アルゴリズム一個覚えるのってしんどいですね。
もっと数学勉強しておけばよかった。

社会に出てから使わないじゃんってことは
ないんじゃないかなーって思いました。
そう思う頃には、時既に遅しなんですよね。

とゆーわけで、今回はこんな感じで書きました。
読んでくれた人ありがとうございました。

<br />
$ar = array();</p>
<p>for($i=0; $i&lt;1000; $i++)<br />
{<br />
     $ar[] = rand(1,1000);<br />
}</p>
<p>$quick = new SortQuick($ar);</p>
<p>class SortQuick<br />
{</p>
<p>     public $result = array();</p>
<p>     function __construct($data)<br />
     {<br />
          $arcount = count($data);<br />
          $R = $arcount-1;<br />
          $L = 0;<br />
          $this-&gt;Main($data,$L,$R);<br />
          //$this-&gt;output($this-&gt;result); 訂正 5/27<br />
     }</p>
<p>     private function main(&amp;$data,$L,$R)<br />
     {</p>
<p>          $pivot = $data[$L];</p>
<p>          $i=$L;<br />
          $j=$R;</p>
<p>          while(1)<br />
          {<br />
               while($data[$i]&lt;$pivot) { $i++; }<br />
               while($data[$j]&gt;$pivot) { $j--; }</p>
<p>               if($i&gt;=$j){<br />
                    $this-&gt;result = $data;<br />
                    break;<br />
               };               </p>
<p>               $tmp = $data[$i];<br />
               $data[$i] = $data[$j];<br />
               $data[$j] = $tmp;</p>
<p>               $i++;<br />
               $j--;<br />
          }</p>
<p>          if($i-1&gt;$L)<br />
          {<br />
               $this-&gt;main($data,$L,$i-1);<br />
          }</p>
<p>          if($j+1&lt;$R)<br />
          {<br />
               $this-&gt;main($data,$j+1,$R);<br />
          }</p>
<p>     }</p>
<p>/* 訂正 5/27<br />
     private function output($o)<br />
     {<br />
          echo &quot;&lt;pre&gt;&quot;;<br />
          print_r($o);<br />
          echo &quot;&lt;/pre&gt;&quot;;<br />
     }<br />
*/<br />
}</p>
<p>echo &quot;&lt;pre&gt;&quot;;<br />
var_dump($quick-&gt;result);<br />
echo &quot;&lt;/pre&gt;&quot;;<br />

とりあえず動きました。

関連記事

  1. PHPサムネイル
  2. PHPサムネイル
  3. PHPサムネイル

コメントをお待ちしております