Re: forth Insertion Sort

Yes he did, but I am unable to find a FORTH that will run the solution.
Gforth get's all the way to the :noname definition and then errors on
"third" (Line 63). Win32Forth errors on "postpone i' " (Line 14). Mr.
Melice example is great as he describes in detail the how and why, I
just can't seem to be able to execute it.

All suggestion Appreciated.

<For Reference >
\ INSERTION-SORT sample.

\ COMPARE: returns...
\ -1 if array[i] < array[j]
\ 0 if array[i] = array[j]
\ +1 if array[i] > array[j]
defer compare-key ( array i j -- result )

\ EXCHANGE array[i], array[j].
defer swap-data ( array i j -- )

\ TOOL: in a DO..LOOP, II returns the descendant index.
: ii ( -- index )
postpone i'
postpone i
postpone -
postpone 1- ; immediate

\ ---------------------------------

\ WHILE array[i+1]<array[i] AND i>=0, Swap(array[i], array[i+1]), i=i-1

\ There is another, faster way; not using SWAP-DATA:
\ TEMP=array[i+1]
\ WHILE I>=0 AND array[i+1]<array[i] DO array[i+1]=array[i], i=i-1
\ array[i+1]=TEMP
: move-key-down ( array index -- )
0 ?do
dup ii dup 1+ ( array i i+1 )
compare-key 0< ( array pair-sorted? )
if leave then
dup ii dup 1+ swap-data
loop drop ;

\ Find the first non-sorted pair, then MOVE-KEY-DOWN.
: insertion-sort ( array count -- )
1 ?do
dup i dup 1- compare-key 0< if
dup i move-key-down
then
loop drop ;

\ -----------------------
\ Test a bit complicated because I don't use specialized array access
word.

create myarray
here
9 , 3 , 4 , 12 , 7 , 1 , 4 , 3 , 2 ,
here swap - cell / constant mycount

:noname [ is compare-key ] ( array i j-- result )
cells third + @ >r cells + @ r>
( a b ) 2dup > if 2drop 1 else < then ;

:noname [ is swap-data ] ( array i j -- )
cells third + >r cells + r> ( a' b' )
2dup @ >r @ swap ! r> swap ! ;

: test
myarray mycount insertion-sort
cr
myarray mycount 0 ?do @+ . loop drop
cr ;

.

Relevant Pages

  • [sftalk] Re: Forth Insertion sort (Research Paper)
    ... defer compare-key (array i j -- result) ... dup ii dup 1+ swap-data ... myarray mycount insertion-sort ...
    (comp.lang.forth)
  • Re: The Right Tool
    ... Articles are stored in some ... fixed a number of UTF-8 related bugs, ... DOES> dup cell+ swap perform; ... '%' parse postpone SLiteral postpone type ...
    (comp.lang.forth)
  • Re: Re. Decision-table implementation ?
    ... CELLS constant b ... and then b X would execute p ... you know the size of a line of array, you can make a 2D array by slicing ... DUP alpha IF DROP c EXIT THEN ...
    (comp.lang.forth)
  • Re: Null object = Zero
    ... copy 4 exch putinterval pop ... dup 0 8 getinterval ... A generic version for any array length: ... % Even works with strings, ...
    (comp.lang.postscript)
  • Re: Distinguishing DOES>
    ... ' POSTPONE and friends are then redefined to return the appropriate behavio= ... Are you thinking of implementing INTERPRET/COMPILE: ... ' DUP ' COMPILE, clone URCLONE ...
    (comp.lang.forth)