Search code examples
arrayssortingforth

How do you in-place sort an array of integers in Forth?

I have a 100 element array of integers. Let's say it uses this definition for array:

: array ( n "name" -- )
     create cells allot
     does> ( index -- addr ) swap cells + ;
100 array atod             \ Make an array with 100 cells
3 atod                     \ Return address of fourth element

Now let's say this atod array has been filled in with 100 integer values read from an ATOD input. And before I process it, I want to permanently sort the integers by value using the same atod array. That is, I don't care about the original order, I just care that they are sorted, and my memory is slim so I'd prefer not to define any other variables or arrays.

How do you sort it?

EDIT: Fixed the array definition as per @Julian Fondren.

Solution

  • Your definition of ARRAY is wrong:

    does> cells + ;

    At DOES> , the address of the array is on top of the stack, and the index (e.g. 3 in 3 atod) is below it. So your CELLS operates on the address, which is a pretty meaningless operation, and the result is then added to 3. By convention, the address is ignored in DOES> stack pictures, since stack pictures are intended for the user of the word. But the address is there.

    Correctly,

    : array ( n "name" -- )
  create  cells allot
  does> ( index -- addr ) swap cells + ;

    And you sort it like you sort anything. Really, there is a whole literature of sorting operations, and all of it applies to Forth. So quicksort, insertion sort, bogosort, whatever, you can do it in Forth.

    There are a whole bunch of sorting examples listed at

    http://rosettacode.org/wiki/Category:Forth

    Quicksort is a destructive (you don't care about the original order) in-place (you don't want to allocate a bunch of extra memory) sort that meets your criteria. Rosetta Code has a Forth implementation here:

    http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Forth

    (That code defers LESSTHAN as quicksort implementions usually do in other languages, but the Forth code has more places that make assumptions about the type of the data that other languages usually would have, so deferring LESSTHAN is not sufficient to make a generic sort.)