Sorting an array of strings in Forth

Question

I have used CREATE to create an array of strings:

create mystringarray s" This" , s" is" , s" a", s" list" ,

And I want to sort this in ascending order. I've found some tutorials for assembly language online, but I want to do it in Forth. What is the best practice method?

Answer 1

You need to first make sure that your data representation is accurate.

A literal string in Forth is obtained using the word s" and so you would write, for example:

s" This"  ok

Once entered, if you do .s, you'll see two values:

.s <2> 7791776 4  ok

This is a pointer to the actual string (array of characters), and a count of the number of characters in the string. Certain words in Forth understand this string representation. type is one of them. If you now entered type, you'd get the string typed on the display:

type This ok

So now you know you need two cells to represent a string obtained by s". Your create needs to take this into account and use the 2, word to store 2 cells per entry, rather than , which stores only one cell:

create myStringArray
    s" This" 2,
    s" is" 2,
    s" an" 2,
    s" array" 2,
    s" of" 2,
    s" strings" 2,

This is an array of address/count pairs for the strings. If you want to access one of them, you can do so as follows:

: myString ( u1 -- caddr u1 )  \ given the index, get the string address/count
    \ fetch 2 cells from myStringArray + (sizeof 2 cells)*index
    myStringArray swap 2 cells * + 2@ ;

Breaking this down, you need to take the base of your array variable, myStringArray and add to it the correct offset to the string address/count you want. That offset is the size of an array entry (2 cells) times the index (which is on the data stack). Thus the expression, myStringArray swap 2 cells * +. This is followed by 2@ which retrieves the double word (address and count) at that location.

Put to use...

3 myString type array ok
0 myString type This ok

etc...

Now that you know the basics of indexing the array, then the "best practice" of sorting would follow the normal best practices for choosing a sort algorithm for the kind of array you wish to sort. In this case, a bubble sort is probably appropriate for a very small array of strings. You would use the compare word to compare two strings. For example:

s" This" 0 myString compare .s <1> 0  ok

Result is 0 meaning the strings are equal.