PHP クイックソート

基本情報で出てきた問題

・平成27年春期 データ構造とアルゴリズム
・問題にあるプログラムをPHPのコードにしてみた

PHPで書いてみた

<?php

$array = [5,3,6,4,7,2,1]; //任意の配列
$K = 4; //何番目の値を取りたいか

//標準入力を使いたい場合上記をコメントアウトして、書き部分をコメントアウト外す
// $array = explode(",", trim(fgets(STDIN))); //カンマ区切りで入力する
// foreach($array as $v){
//     if(!is_numeric($v)) {
//         echo '数値以外が含まれています';exit;
//     }
// }
// $K = trim(fgets(STDIN)); //何番目の値を出力したいか
// if(!is_numeric($K) || $K <= 0 || $K > count($array)){
//     echo '範囲外です';exit;
// }


$n = count($array);
$top = 0;
$last = $n-1;
$k = $K-1;

$ans = quicksort($array, $k, $top, $last);
echo $ans;

function quicksort($array, $k, $top, $last){
    while($top < $last){
        $pivot = $array[$k];
        $i = $top;
        $j = $last;
        while(true){
            while($array[$i] < $pivot){
                $i++;
            }
            while($pivot < $array[$j]){
                $j--;
            }
            if($i >= $j){
                break;
            }
            $work = $array[$i];
            $array[$i] = $array[$j];
            $array[$j] = $work;
            $i++;
            $j--;
        }
        if($i <= $k){
            $top = $j + 1;
        }
        if($k <= $j){
            $last = $i - 1;
        }
    }
    return $array[$k];
}

感想

・今回は値を出力しただけだが、並び替えられた配列を取得したりもできそう
・標準入力を使った場合を入れてみた