PHP에서 빠른 정렬 비재귀 알고리즘을 구현하는 방법

소개

퀵 정렬은 배열을 두 개의 하위 배열로 연속적으로 나누어 정렬을 수행하는 효율적인 정렬 알고리즘입니다. 퀵소트 알고리즘에서는 피벗 값이 선택되고 피벗 값보다 작은 모든 요소는 왼쪽에 배치되고 피벗 값보다 큰 모든 요소는 오른쪽에 배치됩니다. 그런 다음 이 프로세스는 전체 배열이 정렬될 때까지 왼쪽 및 오른쪽 하위 배열에 반복적으로 적용됩니다.

퀵 정렬은 원래 문제를 두 개의 작은 하위 문제로 분해한 다음 이러한 하위 문제를 재귀적으로 해결하여 원래 문제를 해결해야 하기 때문에 재귀 함수입니다. 이 접근 방식은 일부 상황에서는 효과적으로 작동할 수 있지만 몇 가지 제한 사항이 있습니다. 특히 대규모 배열을 처리할 때 재귀 알고리즘이 컴퓨터의 스택 공간을 모두 소모하여 스택 오버플로 예외가 발생할 수 있습니다. 또한 재귀 함수 호출의 추가 오버헤드로 인해 알고리즘 성능이 저하될 수도 있습니다.

따라서 어떤 경우에는 비재귀적 구현 방법을 사용하는 것이 더 적절할 수 있습니다. 이번 글에서는 PHP를 이용한 퀵 정렬을 위한 비재귀 알고리즘을 소개하겠습니다.

알고리즘 구현

먼저 배열을 두 개의 하위 배열로 나누는 데 사용되는 보조 함수 파티션을 정의합니다. 하나는 기준 값보다 작은 모든 요소를 ​​포함하고 다른 하나는 기준 값보다 큰 모든 요소를 ​​포함합니다.

function partition(&$arr, $left, $right) {
    $pivot = $arr[$right]; // 选择最后一个元素作为基准值
    $i = $left - 1;
    for ($j = $left; $j < $right; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;
            list($arr[$i], $arr[$j]) = array($arr[$j], $arr[$i]); // 交换i和j处的元素
        }
    }
    list($arr[$i + 1], $arr[$right]) = array($arr[$right], $arr[$i + 1]); // 将基准值放到正确的位置
    return $i + 1;
}

이 함수는 배열의 마지막 요소를 기준 값으로 선택하고 배열 요소를 교환하여 기준 값보다 작은 모든 요소를 ​​배열의 왼쪽에 배치합니다. 이 과정에서 변수 $i를 사용하여 현재 처리 중인 하위 배열의 첨자를 기록하고, $j를 사용하여 전체 배열을 순회합니다. 피벗 값보다 작은 요소를 찾으면 $i를 오른쪽으로 한 위치 이동하고 해당 요소를 $i의 위치에 배치합니다. 마지막으로 최종 위치 $i + 1에 기본 값을 배치합니다.

파티션 기능을 사용하면 이제 퀵 정렬 알고리즘의 비재귀 버전을 구현할 수 있습니다. 이 버전에서는 스택을 사용하여 처리할 하위 배열을 저장합니다. 하위 배열을 처리할 때 먼저 스택에 하위 배열의 왼쪽 및 오른쪽 경계를 기록한 다음 모든 하위 배열이 정렬될 때까지 이를 두 개의 작은 하위 배열로 계속 나눕니다.

function quick_sort(&$arr) {
    $stack = new SplStack(); // 使用SplStack实现栈
    $stack->push(count($arr) - 1); // 将整个数组的下标压入栈
    $stack->push(0);
    while (!$stack->isEmpty()) {
        $left = $stack->pop();
        $right = $stack->pop();
        $pivotIndex = partition($arr, $left, $right);
        if ($left < $pivotIndex - 1) {
            $stack->push($pivotIndex - 1);
            $stack->push($left);
        }
        if ($pivotIndex + 1 < $right) {
            $stack->push($right);
            $stack->push($pivotIndex + 1);
        }
    }
}

이 버전의 코드에서는 SplStack 클래스를 사용하여 스택을 구현합니다. 먼저 전체 배열의 왼쪽 및 오른쪽 경계를 스택에 푸시한 다음 스택에서 왼쪽 및 오른쪽 경계를 지속적으로 제거하고 이를 파티션 함수에 전달하여 하위 배열을 나눕니다. left < 마찬가지로,ivotIndex + 1 < right이면 오른쪽 하위 배열이 아직 정렬되지 않았으며 처리를 위해 스택으로 푸시된다는 의미입니다.

이 알고리즘의 시간 복잡도는 O(nlogn)입니다. 모든 경우에 퀵 정렬의 재귀 버전만큼 빠르지는 않지만 알고리즘의 공간 복잡성을 크게 줄이고 재귀 함수 호출의 오버헤드를 피할 수 있습니다. PHP에서 큰 배열을 빠르게 정렬해야 하는 경우 이 알고리즘이 빠른 정렬의 재귀 버전보다 사용자의 요구에 더 적합할 수 있습니다.

위 내용은 PHP에서 빠른 정렬 비재귀 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!