중간값 구하기

이문제는 소트프로그램을 만들라는 거군요

<?php

set_time_limit(0);
//ini_set('memory_limit','1G');
header('Content-Type: text/html; charset=utf-8');



function microtime_float() {

list($usec, $sec) = explode(" ", microtime());
return (((float)substr((string)$usec, 0, 4) + (float)$sec)) * 1000;
}



function get_excute_time($msg, $start_time){

$end_time = microtime_float();
$time = ($end_time - $start_time) / 1000;

echo "$msg : $time seconds" . PHP_EOL ;
}



$input = 1000;

//임의의 $input 이하의 숫자 $input개 뽑음
$numbers = Array();

while(1) {

if (count($numbers) == $input)
break;

$numbers[] = rand(1, $input);
}

//print_r($numbers);
//echo PHP_EOL;

$start_time = microtime_float();


$result_low = $result_high = Array();
while(1){

$min = 999999999;
$x = 999999999;

$max = 0;
$y = 999999999;
foreach($numbers as $k => $v){

if ($v < $min) {

$min = $v;
$x = $k;
}

if ($v > $max) {

$max = $v;
$y = $k;
}
}

if ($min != 999999999 && $min > 0) {

$result_low[] = $min;
unset($numbers[$x]);
}

if ($max != 0 && $max > 0 && $x != $y) {

$result_high[] = $max;
unset($numbers[$y]);
}

if (count($numbers) == 0)
break;
}

$result = $result_low;

$high_cnt = count($result_high);
for ($i = $high_cnt - 1; $i >= 0; $i--) {

$result[] = $result_high[$i];
}
//print_r($result);
//echo PHP_EOL;

$cnt = count($result);
if ($cnt % 2 == 0) {//짝수

echo $result[$cnt / 2 - 1];
}
else {//홀수

echo $result[floor($cnt / 2)];
}

echo PHP_EOL;



get_excute_time("진행 시간", $start_time);

?>

491
진행 시간 : 0.05 seconds

// 계수 정렬(Counting Sort) 알고리즘 적용
function get_middle($arrNum){
$count = array();
$max = - 1;
$cnt = 0;
foreach ($arrNum as $k => $v) {
if ($max < $v) $max = $v;
$count[$v]++;
$cnt++;
}

for ($i = 1; $i <= $max; $i++)
$count[$i] += $count[$i - 1];

$result = array();
for ($i = $cnt -1; $i >= 0; $i--)
$result[--$count[$arrNum[$i]]] = $arrNum[$i];

return $result[ceil($cnt / 2 - 1)];
}

제 것 보다 훨씬 좋네요. ^^

수고하셨습니다.

굳이 세번째 루프 까지 갈필요는 없어 보입니다.

// 계수 정렬(Counting Sort) 알고리즘 적용
function get_middle($numbers){

$result = $count = array();
$max = - 1;
$min = null;

foreach ($numbers as $k => $v) {

if ($max < $v)
$max = $v;

if (is_null($min) || $min > $v)
$min = $v;

$count[$v] = (isset($count[$v])) ? $count[$v] + 1 : 1;
}

for ($i = $min; $i <= $max; $i++) {

if (isset($count[$i]) && $count[$i] > 0) {

for ($j = 0; $j < $count[$i]; $j++) {

$result[] = $i;
}
}

}

return $result[ceil($cnt / 2 - 1)];
}

잘 배웠습니다.

// 제 소스보다 훨씬 빠르군요. 대단하십니다.
// 유창화님 소스에서 중간값이 나오면 루프를 더 돌지 않고 값을 return 하도록 수정해 보았습니댜.
function get_middle($numbers){

$result = $count = array();
$max = - 1;
$min = null;
$cnt = 0;

foreach ($numbers as $k => $v) {
$cnt++;

if ($max < $v)
$max = $v;

if (is_null($min) || $min > $v)
$min = $v;

$count[$v] = (isset($count[$v])) ? $count[$v] + 1 : 1;
}
$mid = ceil($cnt / 2 - 1);

for ($i = $min; $i <= $max; $i++) {

if (isset($count[$i]) && $count[$i] > 0) {

for ($j = 0; $j < $count[$i]; $j++) {

$result[] = $i;
if (isset($result[$mid])) return $result[$mid];

}
}

}
}

네 ㅎㅎ
이게 정답이네요.
수고하셧습니다. ^^

감사합니다.
유창화님 차려놓은 밥상에 숱가락만 언졌습니댜. ^^

너무나도 좋은 답변들 너무 감사합니다!!

두분의 깔끔한 정리 ~ 너무 좋습니다!