大きなソート配列の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

はい、クイックソートは、単純な実装ではエッジケースでリターンスタックオーバーフローの対象となることが知られています。この解決策も知られています。再帰のために小さな部分を使用し、テールコールのためにもう1つの部分を使用します。ああ、this recipeはすでにあまりにもウィキペディアで説明されています

その後、 に再帰する末尾呼び出しを使用し、ほとんどのO（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 
;