【シェルソート】FINAL問題 シェルソート (paizaランク B 相当) 解答例 – PHP編【効率的なソートアルゴリズムメニュー】
【効率的なソートアルゴリズムメニュー】 > 【シェルソート】FINAL問題 シェルソート (paizaランク B 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。
解答例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
<?php $input = trim(fgets(STDIN)); $array = explode(" ",trim(fgets(STDIN))); $k = trim(fgets(STDIN)); $harray = explode(" ",trim(fgets(STDIN))); $log; function insertion_sort($a, $n, $h){ // アルゴリズムが正しく実装されていることを確認するために導入するカウンタ変数、ソート処理には関係がないことに注意 $num_of_move = 0; //print_r($a); for($i = $h;$i < $n; $i++){ // A[i] を、整列済みの A[i-ah], ..., A[i-2h], A[i-h] の適切な位置に挿入する // 実装の都合上、A[i] の値が上書きされてしまうことがあるので、予め A[i] の値をコピーしておく $x = $a[$i]; // A[i] の適切な挿入位置を表す変数 j を用意 $j = $i - $h; // A[i] の適切な挿入位置が見つかるまで、A[i] より大きい要素を後ろにずらしていく while($j >= 0 && $a[$j] > $x){ $a[$j + $h] = $a[$j]; $j -= $h; $num_of_move++; } // A[i] を挿入 $a[$j + $h] = $x; } echo $num_of_move."\n"; //print_r($a); return $a; } function shell_sort($a, $n, $h , $k){ for($i = 0;$i < $k;$i++){ if($i == 0){ $d = insertion_sort($a , $n , $h[$i]); //print_r($d); } else { $d = insertion_sort($d , $n , $h[$i]); } } } shell_sort($array , $input , $harray ,$k); ?> |
