4

クイックソートを使用して、スタック上のエントリによって表されるセット内の要素である整数を並べ替えます。たまたますでにソートされているより大きな（約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 ;

リターンスタックでオーバーフローする可能性はありますか? 配列がソートされているかどうかをプログラムが追跡することは事実上不可能です。では、問題を解決するにはどうすればよいでしょうか?

4

1 に答える 1

4

はい、クイックソートは、単純な実装のエッジ ケースでリターン スタック オーバーフローの対象となることが知られています。解決策も知られています。再帰には小さい部分を使用し、末尾呼び出しには別の部分を使用します。ああ、このレシピはすでにウィキペディアにも記載されています。

最大で 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
;
于 2016-08-19T00:32:15.767 に答える