練習問題03

Question

下記のような問題があります。
皆さんはどのように解かれますか？
わたしのコードを記載しますので、突っ込みやアドバイスなどあればご教示頂けると助かります。
もっと簡単だよ、こんな関数あるよとかあれば宜しくお願い致します。

問題
以下のPHPプログラムで定義される配列がある。
$array = array(50, 37, 29, 59, 31, 88, 48, 87, 3, 63);
PHPの内部関数でソートせず、小さいものから順に出力せよ。

$rarray = array(50, 37, 29, 59, 31, 88, 48, 87, 3, 62);

$length = count($rarray);

trace($rarray);
for ($i = 0; $i < $length; $i ++) {
        for ($j = $i + 1; $j < $length; $j++) {
                if ($rarray[$i] > $rarray[$j]) {
                        $tmp = $rarray[$i];
                        $rarray[$i] = $rarray[$j];
                        $rarray[$j] = $tmp;
                        trace($rarray, $i, $j);
                }
        }
}

foreach ($rarray as $value) {
        echo $value . "\n";
}

function trace($arr, $i = 0, $j = 0) {
        echo "($i,$j)";
        foreach ($arr as $value) {
                echo $value . ",";
        }
        echo "\n";
}

考え方
例1)自分で配列を小さい順から並ぶように入れ替えてから、for文を使って出力(echo)する。
例2)「配列の中で一番小さい数を出力して、その数を配列から削除する」操作を、
配列が空になるまで繰り返す。
例3)左右で値を比較して、小さい数を左に置いていくいくようにする。

Answer 1

例2をコードに落としてみました。

$array = array(50, 37, 29, 59, 31, 88, 48, 87, 3, 63); 
while ($array){
  $min_number = min($array);
  echo ($min_number);
  $array = array_diff($array, array($min_number));
}

Answer 2

この手の問題は、ソートアルゴリズムとして、いくつかパターンがあります。
返答方法としては邪道かもしれませんが、下記ページに最速のアルゴリズムとしてクイックソートのソースが書いてありますので、載せておきます。

http://qiita.com/kiimiiis/items/845181f9a81a674ffe96

Answer 3

私も例３でやってみました。

結構邪道かも。
でも配列の中身の入れ替えはPHPらしくやってます。

$rarray = array(50, 37, 29, 59, 31, 88, 48, 87, 3, 62);
$notyet = 1; //ソートが終わったかどうかを判断

while ($notyet == 1) {//dosortで書き換えがなくなるまでは続ける。
    $notyet = dosort($rarray);
}

print implode("\n", $rarray);
print "\n";
exit;

function dosort(&$rarray) {
    $found = 0;
    foreach ($rarray as $key => $val) {
        if ($key == count($rarray) - 1) { //配列の最後
            break;
        }
        if ($val > $rarray[$key + 1]) {
            //ここで中身の入れ替え
            list($rarray[$key], $rarray[$key + 1]) = array($rarray[$key + 1], $rarray[$key]);
            $found = 1; //一回でも書き換えがあったらフラグを立てる
        }
    }
    return $found;//ここで0が帰ればソート終了
}

Answer 4

例3を再帰関数で実行してみました。
考え方（例3）的にもプログラム的にも分かりやすいと思いますよ！

$array = [ 50, 37, 29, 59, 31, 88, 48, 87, 3, 63 ];

// 並び替え
recursive( $array );

//出力
foreach( $array as $value ) {
	print( "$value\n" );
}

// 関数群
function recursive( &$array, $i = 0, $j = 0 ) {
	if ( count( $array )-1 === $i ) {
		return;
	}
	if ( $array[ $i ] > $array[ $j ] ) {
		swap( $array[ $i ], $array[ $j ] );
	}

	if ( count( $array )-1 === $j ) {
		$i++;
		$j = $i;
	}
	recursive( $array, $i, $j+1 );
}

function swap( &$a, &$b ) {
	$t = $b;
	$b = $a;
	$a = $t;
}