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 ;

难道return栈溢出了？数组排序与否，程序几乎不可能保持跟踪，那么如何解决这个问题？

Answer 1

是的，已知 Quicksort 是 return 天真的实现中边缘情况下堆栈溢出的主题。解决方案也是众所周知的：使用较小的部分进行递归，使用另一部分进行尾调用。哦，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.

尾调用优化将调用转换为跳转，因此它不使用 return 堆栈。

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

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

Problems with quicksort in Forth for big sorted arrays

forth

gforth