Проблемы с быстрой сортировкой в ​​Forth для больших отсортированных массивов

Question

Я использую Quicksort для сортировки целых чисел, являющихся элементами в наборах, представленных элементами в стеке. Он работает нормально, за исключением случаев, когда ему приходится сортировать более крупные (около 10000 элементов), которые уже сортируются.

: 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

Да, Quicksort, как известно, является объектом переполнения стека возврата в крайних случаях в наивной реализации. Решение также известно: используйте меньшую часть для рекурсии и другую часть для вызова хвоста. О, this recipe уже описано в Википедии тоже:

Чтобы убедиться в наиболее O (журнал N) используется пространство, рекурсию первый в меньшую сторону перегородки, а затем использовать хвост вызов рекурсии в другой.

Оптимизация звонков позволяет преобразовать вызов в прыжок, поэтому он не использует стек возврата.

qsort Обновлено определение:

: 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 
;