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

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

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