Probleme mit Quicksort in Forth für große sortierte Arrays

Question

Ich verwende Quicksort, um Ganzzahlen zu sortieren, die Elemente in Sätzen sind, die durch Einträge auf einem Stapel dargestellt werden. Es funktioniert in Ordnung, außer wenn es größere (ungefähr 10.000 Elemente) Sätze sortiert, die zufällig bereits sortiert sind.

: 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 ; 

Könnte es im Rücklaufstapel zu einem Überlauf kommen? Es ist praktisch unmöglich für das Programm, in der Spur zu bleiben, wenn das Array sortiert ist oder nicht, also wie man das Problem löst?

Answer 1

Ja, Quicksort ist bekannt, dass ein Thema der Rücksprung-Stack-Überlauf in den Rand Fällen in naiven Implementierung. Die Lösung ist auch bekannt: Verwenden Sie einen kleineren Teil für die Rekursion und einen anderen Teil für den Tail Call. Oh, ist this recipe bereits in Wikipedia auch beschrieben:

Um sicherzustellen, höchstens O (log n) Raum verwendet wird, Rekursion zuerst in die kleinere Seite der Trennwand, dann einen Endaufruf verwenden, um Rekursion in das andere.

Die Tail-Call-Optimierung wandelt einen Aufruf in einen Sprung um, sodass der Rückgabe-Stack nicht verwendet wird.

qsort Definition aktualisiert:

: 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 
;