큰 정렬 된 배열에 대한 quicksort의 문제점

Question

Quicksort를 사용하여 정수를 스택의 항목으로 표시된 집합의 요소로 정렬합니다. 이미 정렬 된 큰 (약 10,000 요소) 집합을 정렬해야 할 때를 제외하고는 아무 문제가 없습니다.

: adswap \ ad1 ad2 -- 
    over @ over @ swap rot ! swap ! ; 

: singlepart \ ad1 ad2 -- ad 
    tuck 2dup @ locals| p ad | swap    \ ad2 ad2 ad1 
    do i @ p <          \ ad2 flag 
    if ad i adswap ad cell + to ad then cell \ ad2 cell 
    +loop ad adswap ad ;       \ ad 

: qsort \ ad1 ad2 --  pointing on first and last cell in array 
    2dup < 
    if 2dup singlepart >r 
    swap r@ cell - recurse 
    r> cell + swap recurse 
    else 2drop 
    then ; 

리턴 스택에서 오버플로가 될 수 있습니까? 배열이 정렬되거나 정렬되지 않을 때 프로그램이 계속 추적하는 것이 사실상 불가능합니다. 그래서 문제를 해결하는 방법은 무엇입니까?

Answer 1

예, 퀵소트는 순진한 구현에서 엣지 케이스의 리턴 스택 오버 플로우의 대상으로 알려져 있습니다. 이 솔루션은 또한 재귀를 위해 작은 부분을 사용하고 꼬리 호출을 위해 다른 부분을 사용합니다. 아, this recipe 이미 너무 위키 백과에 설명되어 있습니다 :

는 O (로그 n) 공간을 사용하는 파티션의 작은 측에 첫 번째 재귀 대부분에서 확인하려면 다음 로 재귀하는 꼬리 호출을 사용 다른 하나.

꼬리 호출 최적화는 호출을 점프로 변환하므로 리턴 스택을 사용하지 않습니다.

: qsort \ ad1 ad2 --  pointing on first and last cell in array 
    begin 
    2dup < 0= if 2drop exit then 
    2dup - negate 1 rshift >r \ keep radius (half of the distance) 
    2dup singlepart 2dup - >r >r \ (R: radius distance2 ad) 
    r@ cell - swap r> cell+ swap \ (d-subarray1 d-subarray2) 
    2r> u< if 2swap then recurse \ take smallest subarray first 
    again \ tail call optimization by hand 
;