Insertion sort (Forth)
From LiteratePrograms
- Other implementations: ACL2 | C | C, simple | Eiffel | Erlang | Forth | Haskell | Io | Java | Lisp | OCaml | Python | Python, arrays | Ruby | Scala, list | Smalltalk | Standard ML | Visual Basic .NET
The insertion sort is one of the simpler sorts to implement. This version uses a linear search to find the proper place to insert each item into the sorted portion of the array. Since that portion is sorted, it could be replaced with a binary search.
insert takes the next item to be sorted (located at end), finds where to store it in the sorted portion of the array (start...end), and inserts it at that position, resulting in a sorted portion that is one element longer than before.
The while loop decrements the end parameter searching for the proper insertion point within the array for the value initially at end. This loop has two possible termination conditions:
- 2dup < checks whether the entire array has been searched (start < insertion point). This will only be true if the value (r@) is less than all other elements already in the sorted array.
- r@ over cell- @ < checks whether the value at end (stored on the return stack with dup @ >r) is less than the previous position in the array.
If neither termination condition is met then we
- cell- look one cell earlier in the array and
- dup @ over cell+ ! move that value to where we did the comparison.
The final clause (r> swap !) puts the value at the insertion point, restoring the return stack. The effect of the repeated moves is like a rotation:
Before: ... [ i ] [i+1] ... [e-1] [end] After: ... [end] [ i ] [i+1] ... [e-1]
A Forth detail: each extra while in a begin...while...repeat loop requires a matching terminal then to balance the control structure.
<<insert>>= : cell- 1 cells - ; : insert ( start end -- start ) dup @ >r ( r: v ) begin 2dup < while r@ over cell- @ < while cell- dup @ over cell+ ! repeat then r> swap ! ;
sort loops along the unsorted portion of the array, inserting items into the sorted beginning of the array.
<<sort>>= : sort ( array len -- ) 1 ?do dup i cells + insert loop drop ;
The test routine takes an unsorted ten element array, sorts it, and prints it now in ascending order.
<<insertion-sort.fs>>= insert sort create test 7 , 3 , 0 , 2 , 9 , 1 , 6 , 8 , 4 , 5 , : main test 10 sort 10 0 do test i cells + @ . loop cr ; main bye
| Download code |