在Forth中对大排序数组进行快速排序的问题

Question

我使用快速排序对整数进行排序，这些整数是由堆栈上的条目表示的集合中的元素。它可以正常工作，除非它必须对较大的(大约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

是的，在幼稚实现的边缘情况下，快速排序是已知的返回堆栈溢出的主题。解决方案也是已知的:使用较小的部分用于递归，另一部分用于尾部调用。哦，这个食谱在维基百科上也有描述:

为了确保最多使用O(log 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
;