forth - Forth 中大排序数组的快速排序问题

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维基百科中也已经描述过:

To make sure at most O(log n) space is used, recurse first into the smaller side of the partition, then use a tail call to recurse into the other.

尾调用优化将调用转化为跳转，因此不使用返回栈。

更新 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
;