PHP 備忘録 | メシのタネ

ahiru
このエントリーをはてなブックマークに追加

バブルソートをPHPでやってみた

 2014/05/14

<問題>
隣り合う配列の大小を並び替えて値の小さい順に数字を出力してください。

$ar = array(10,65,8,56,32,5,89,3,121,1,5);

自力で書く必要が無いから、別に覚えなくて良いと思ってました。
だけど、多分アルゴリズムやった方が良い理由は過程だと思うんです。

配列の中身を大きいのと小さいの入れ替えるアルゴリズムですけど、
それを実現する際に、ああでもないこうでもないって考えた努力こそが大事だと思うので、
もう既に定義済み関数であるソートであったとしても頑張る必要が僕はあると思います。

バブルソートとは

隣の配列の値と比較して、
指定した条件により配列の入れ替えを行う
配列の交換方法であると思います。

入れ子になったループの回数を決定

1回のループで、(配列数-現在のループ回数)分の入れ替え処理がされます。
これを配列回数分ループしてる最中に(配列数-現在のループ回数)分繰り返すと
昇順に並んだ配列が出来上がります。

なので、入れ子になったfor分の目標値の設定をします。
2回目のループ回数 = (配列数-現在のループ回数)

     for($i=0; $i<count($ar); $i++)
     {
          $target = count($ar)-$i;
     }

for文の中にfor文を書く

for文の中にfor文を書きます。
変数jの初期値が1なのは、一個前の配列と比較する為です。
初期値が0スタートだった場合、未定義の配列にアクセスするので
こうやってます。

     for($i=0; $i<count($ar); $i++)
     {
          $target = count($ar)-$i;
          for($j=1; $j<$target; $j++)
          {
               
          }
     }

値の大小を入れ替える

ループ回数jを配列の添え字にして、
配列の中身を見ていきます。
その際に、1個前の配列の中身よりも今のループ回数の配列の中身の数値が
大きい場合に、配列の中身の入れ替えを行います。

条件・配列の中身の入れ替えはこう書きます。

     for($i=0; $i<count($ar); $i++)
     {
          $target = count($ar)-$i;
          for($j=1; $j<$target; $j++)
          {
               if($array[$j]<$array[$j-1])
               {
                    $swap = $ar[$j];
                    $ar[$j] = $ar[$j-1];
                    $ar[$j-1] = $swap;
               }
          }
     }

こうして、1度目のループで配列の数の分だけループ処理が行われ、
(配列の数-入れ替えた配列の数)の分だけもう一度ループ処理を行います。

配列の数が15だとしたら、15回の比較が行われて、条件に合致した物は
入れ替えの処理が行われます。

動作済みコード

今回のコードはこうなります。
上手に説明できない上に、本当にこの説明で正しいのか
心配になりながらデリケートな記事を書きました。
イライラした人居たらごめんなさい。

$ar = array(10,65,8,56,32,5,89,3,121,1,5);

     for($i=0; $i<count($ar); $i++)
     {
          $target = count($ar)-$i;
          for($j=1; $j<$target; $j++)
          {
               if($ar[$j]<$ar[$j-1])
               {
                    $swap = $ar[$j];
                    $ar[$j] = $ar[$j-1];
                    $ar[$j-1] = $swap;
               }
          }
     }

foreach($ar as $val)
{
     echo $val."<br />";
}

ここまで読んでくれた方、どうもありがとうございました!


このエントリーをはてなブックマークに追加

コメント

"バブルソートをPHPでやってみた"
でメシのタネのおすすめを検索したよ!

プログラミング備忘録 | メシのタネ