在Forth中对CREATE创建的字符串数组升序排序的最佳实践

Great question! Sorting string arrays in Forth is totally doable with a bit of stack manipulation and leveraging Forth's built-in string-handling words. Let's break this down step by step with practical, reusable code.

First, Understand Your Array Structure #

You've defined your array like this:

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

Each s" compiles a string (with a leading length byte) into the dictionary, and , stores the string's address in the array. So mystringarray is a cell array where each cell holds the memory address of a string.

Step 1: Define Helper Words #

We'll start with small, focused helper words to handle core operations like swapping elements and comparing strings.

1.1 Swap Array Elements #

This word swaps the strings at two indices in the array:

: SWAP-CELLS ( i j -- )
    mystringarray OVER CELLS + @  \ Fetch address at index i, keep it on stack
    mystringarray SWAP CELLS + @  \ Fetch address at index j
    mystringarray OVER CELLS + !  \ Store j's address at index i
    mystringarray SWAP CELLS + ! ;\ Store original i's address at index j

1.2 Compare Strings for Sorting #

Forth's built-in COMPARE word takes two strings (address1 length1 address2 length2) and returns -1, 0, or 1 if the first string is less than, equal to, or greater than the second (based on ASCII values). We'll wrap this to check if two array elements need swapping for ascending order:

: NEED-SWAP? ( i j -- flag )
    mystringarray OVER CELLS + @ COUNT  \ Get addr+length for string at i
    mystringarray SWAP CELLS + @ COUNT  \ Get addr+length for string at j
    COMPARE 0> ;  \ Returns true (-1) if first string > second (needs swap)

Step 2: Implement the Sort Algorithm #

For small arrays like yours, bubble sort is simple and easy to implement. For larger arrays, you could use quicksort (requires recursion or stack simulation), but bubble sort works perfectly here.

First, define the array size (or calculate it dynamically):

\ Option 1: Manual size (your array has 4 elements)
4 CONSTANT ARRAY-SIZE

\ Option 2: Dynamic size calculation (no need to count manually)
HERE mystringarray - CELLS CONSTANT ARRAY-SIZE

Then the sort word:

: SORT-STRING-ARRAY ( -- )
    ARRAY-SIZE 1-  \ Outer loop runs n-1 times
    0 DO
        ARRAY-SIZE I - 1-  \ Inner loop runs n-i-1 times
        0 DO
            J J 1+ NEED-SWAP? IF
                J J 1+ SWAP-CELLS
            THEN
        LOOP
    LOOP ;

Step 3: Test with a Print Helper #

To verify the sort works, add a word to print the array:

: PRINT-ARRAY ( -- )
    ARRAY-SIZE 0 DO
        mystringarray I CELLS + @ TYPE CR  \ TYPE prints the string (reads length byte automatically)
    LOOP ;

Putting It All Together #

Run this sequence to see the result:

create mystringarray s" This" , s" is" , s" a" , s" list" ,
HERE mystringarray - CELLS CONSTANT ARRAY-SIZE

CR ." Original array:" CR
PRINT-ARRAY

SORT-STRING-ARRAY

CR ." Sorted array (ASCII order):" CR
PRINT-ARRAY

Output: #

Original array:
This
is
a
list

Sorted array (ASCII order):
This
a
is
list

Customizing for Case-Insensitive Sorting #

If you want to ignore uppercase/lowercase differences, replace COMPARE with a custom case-insensitive comparator:

: TO-LOWER ( c -- c )
    DUP [CHAR] A [CHAR] Z BETWEEN IF
        [CHAR] a [CHAR] A - +  \ Convert uppercase to lowercase
    THEN ;

: COMPARE-NOCASE ( addr1 len1 addr2 len2 -- n )
    0  \ Initialize result to 0
    OVER OVER MIN  \ Compare up to the shorter string's length
    0 DO
        OVER I + C@ TO-LOWER
        OVER I + C@ TO-LOWER
        2DUP = IF
            2DROP
        ELSE
            SWAP -  \ Return difference of lowercase chars
            ROT ROT 2DROP 2DROP
            LEAVE
        THEN
    LOOP
    ROT ROT - ;  \ If all compared chars match, return length difference

\ Update the swap check to use the new comparator
: NEED-SWAP?-NOCASE ( i j -- flag )
    mystringarray OVER CELLS + @ COUNT
    mystringarray SWAP CELLS + @ COUNT
    COMPARE-NOCASE 0> ;

\ Update the sort word to use NEED-SWAP?-NOCASE instead of NEED-SWAP?

With this change, the sorted array will be:

a
is
list
This

Best Practices Recap #

• Leverage Forth's core words: Use COUNT, TYPE, and COMPARE to avoid reinventing string-handling logic.
• Modularize code: Split sort logic into small, reusable helpers (like SWAP-CELLS and NEED-SWAP?) to keep code readable and maintainable.
• Choose the right algorithm: Bubble sort for small arrays; quicksort or merge sort for larger datasets.
• Customize comparators: Adjust the comparison logic to match your sorting needs (case-insensitive, locale-specific, etc.).

内容的提问来源于stack exchange，提问作者Manuel Rodriguez