[알고리즘]퀵 정렬(Quick Sort)

<?

// 퀵 정렬(Quick Sort)

function Swap(&$arr, $idx1, $idx2) {

$temp = $arr[$idx1];

$arr[$idx1] = $arr[$idx2];

$arr[$idx2] = $temp; 

}

// 중간값 찾기

function MedianOfThree($arr, $left, $right) {

$samples = array($left, floor(($left+$right)/2), $right);

if ($arr[$samples[0]] > $arr[$samples[1]])

Swap($samples, 0, 1);

if ($arr[$samples[1]] > $arr[$samples[2]])

Swap($samples, 1, 2);

if ($arr[$samples[0]] > $arr[$samples[1]])

Swap($samples, 0, 1);

return $samples[1];

}

function Partition(&$arr, $left, $right) {

$pIdx = MedianOfThree($arr, $left, $right); // 중간값으로 피벗 선택

$pivot = $arr[$pIdx];

$low = $left + 1;

$high = $right;

Swap($arr, $left, $pIdx); // 피벗을 가장 왼쪽으로 이동

while ($low <= $high) { // 교차되지 않을 때까지 반복

// 피벗보다 큰 값을 찾는 과정

while ($low <= $right  && $pivot >= $arr[$low])

$low++;

// 피벗보다 작은 값을 찾는 과정

while ($high >= ($left+1) && $pivot <= $arr[$high])  

$high--;

// 교차되지 않는 상태라면 Swap 실행

if ($low <= $high)

Swap($arr, $low, $high);

}

Swap($arr, $left, $high); // 피벗과 high 가 가리키는 대상 교환

return $high; // 옮겨진 피벗의 위치정보 교환

}

function QuickSort(&$arr, $left, $right) {

if ($left < $right) {

$pivot = Partition($arr, $left, $right); 

QuickSort($arr, $left, $pivot-1);

QuickSort($arr, $pivot+1, $right);

}

}

$arr = array(3, 2, 4, 1, 7, 6, 5);

$len = count($arr);

QuickSort($arr, 0, $len-1);

print_r($arr);

?>