\ qsort.txt  Leo Wong  9 April 02003 fyj +
\ Quicksort qsort
\ Assumes cell-size data or pointers

\ See squabble.txt

include from.txt
from tools.txt

DEFER xch  ( a1 a2 -- )  \ Swap contents of a1 and a2
  ' exchange IS xch

DEFER precedes  ( x1 x2 -- flag )  \ True if x1 and x2 are rigth order
  ' < IS precedes

: sprecedes  ( a1 a2 -- flag )  \ String precedes
   >R COUNT R> COUNT COMPARE 0< ;

: partition ( left right -- l1 r1 l2 r2 )  \ Factor of qsort
   2DUP OVER - 2/ -cell AND +  @ >R  ( R: pivot )
   2DUP BEGIN
     SWAP BEGIN DUP @ R@ precedes WHILE CELL+ REPEAT
     SWAP BEGIN R@ OVER @ precedes WHILE cell- REPEAT
     2DUP U> 0= IF 2DUP xch >R CELL+ R> cell- THEN
   2DUP U> UNTIL R> DROP  SWAP ROT ( smaller-first ) ;

: qsort  ( a1 a2 -- )  \ Sort from a1 to a2
   partition
   2DUP U< IF RECURSE ELSE 2DROP THEN
   2DUP U< IF RECURSE ELSE 2DROP THEN ;

: Quicksort  ( a n -- )  \ Sort n items beginning at a
   DUP 2 < IF 2DROP EXIT THEN
   1- CELLS OVER + qsort ;