5 - Sort

 "The average woman would rather have beauty than brains  because
the average man can see better than he can think."

                YOUR SECOND GFA BASIC 3.XX MANUAL
                             - or -
        HOW I LEARNED TO STOP WORRYING AND LOVE GFA-BASIC
                             PART 6
                       CHAPTER FIVE - SORT
                          by Han Kempen

QSORT v. SSORT

 QSORT  is faster than SSORT,  unless the array is almost  sorted
already. I understand QSORT uses the recursive Quick-sort method,
so  you need more memory than with SSORT (iterative  Shell-sort).
Sort-freaks  can  try to implement sort-algorithms  like  Bubble-
sort,  Selection-sort,  Quick-sort  and Shell-sort with  ordinary
GFA-Basic  commands.  That  doesn't make much sense  if  you  are
sorting  one-dimensional arrays (as in the  following  examples),
but  you could adapt the following for multi-dimensional  arrays.
For one-dimensional arrays you should stick to the fast QSORT (or
SSORT).  Please note (again) that variable-names without  postfix
are word-variables!

 The most popular sort-algorithm probably is the 'Bubble-sort':

     ' Sort word-array numb()
     FOR i=SUB(DIM?(numb()),2) DOWNTO 1
       FOR j=0 TO i
         IF numb(j)>numb(SUCC(j))
           SWAP numb(j),numb(SUCC(j))
         ENDIF
       NEXT j
     NEXT i

 Very simple to program,  but unfortunately very slow. Unless the
array is almost sorted already.

 Almost  as simple as the Bubble-sort,  but much faster,  is  the
'Combsort':

     ' Sort word-array numb()
     last=DIM?(numb())-1
     gap=last
     DO
       gap=MAX(DIV(MUL(gap,8),11),1)         ! gap*8/11 or 1
       CLR switch
       FOR i=0 TO SUB(last,gap)
         j=ADD(i,gap)
         IF numb(i)>numb(j)
           SWAP numb(i),numb(j)
           INC switch
         ENDIF
       NEXT i
     LOOP UNTIL switch=0 AND gap=1

 Other  sort-algorithms  are  even  faster,  but  are  also  more
complicated.  Consult  your favourite Algorithm-gospel  for  more
information about sorting.

QSORT of number-arrays

 Number-arrays  can  be QSORTed (in increasing  order)  in  three
different ways:

     QSORT x&()          ! sorts array; also with x|(), x%() or
                                                             x#()
     QSORT x&(),n        ! sorts elements 0 through n-1
     QSORT x&(),n,y%()   ! elements of index-array y%() are
                                                      swapped too

 In all cases x&(-1) results in sorting in decreasing order.

 The  third  method (with an index-array) is interesting  if  you
need  a  sorted output,  but don't want to  change  the  original
array. You can accomplish this as follows:

     - copy word-array x&() to temporary array temp&()
     - determine index of last element: last=DIM?(temp&())-1
     - create index array: DIM index%(last)
     - fill index-array with index 0 through last
     - sort temporary array: QSORT temp&(),last+1,index%()
     - ERASE temp&()

 The index-array must be an integer-array (postfix %).  Also, the
number  of  elements is not optional if you sort with  an  index-
array.  You can now print the numbers in the original array  x&()
in  increasing  order and you can also save  the  index-array  on
disk:

     FOR i=0 TO last
       PRINT x&(index%(i))
     NEXT i
     '
     BSAVE "INDEX.DAT",V:index%(0),(last+1)*4

QSORT of string-arrays

 A string-array can be sorted in the same three ways as described
for  number-arrays.  If  you  have created  an  index-array  with
last.name$(), you could print an alphabetical list:

     FOR i=0 TO last
       PRINT first.name$(index%(i))'last.name$(index%(i))
     NEXT i

 It's a better idea to create the index-array with the  temporary
string-array complete.name$():

     complete.name$(i)=last.name$(i)+first.name$(i)

 After  sorting,  'Bert Kempen' will now be printed  before  'Han
Kempen'.  If a string-array contains empty strings, these strings
will fill the first elements of the array after sorting.  Usually
you'll DELETE the empty strings before continuing:

     WHILE txt$(0)=""
       DELETE txt$(0)
     WEND

 After deleting the empty strings, the dimension of the array has
not been changed.  Actually, the empty strings have been moved to
the end of the array.

 There  are two extra possibilities with string-arrays.  For  the
first possibility,  create a byte-array and fill with appropriate
ASCII-values:

     DIM ascii|(255)
     ARRAYFILL ascii|(),32    ! CHR$(32) is the space-character
     FOR i=48 TO 57
       ascii|(i)=i            ! 0 - 9
     NEXT i
     FOR i=65 TO 90
       ascii|(i)=i            ! A - Z
     NEXT i
     FOR i=97 TO 122
       ascii|(i)=SUB(i,32)    ! a - z converted to A - Z
     NEXT i

 All  characters that are not numbers or letters will be  treated
as a space (ASCII-value 32). Use the array ascii|() for sorting a
string-array (the use of an index-array is optional):

     QSORT x$() WITH ascii|() [,n[,y%()]]

 Now  'Atari' and 'ATARI' are treated exactly the  same,  because
the  array  ascii|()  is  used  to  convert  lower  case  letters
temporarily to upper case before sorting.  You can even treat the
special characters (ASCII-values above 127) correctly.  Use a few
DATA-lines to add the correct ASCII-values to the array ascii|(),
like this:

    RESTORE ascii.data
    REPEAT
      READ code1,code2
      ascii|(code1)=code2
    UNTIL code1=0
    '
    ascii.data:
    ' format: ASCII-code,replacement
    DATA 128,67,129,85,130,69,131,65,132,65,133,65,134,65,135,67
    '     Ç >C   ü >U   é >E   â >A   ä >A   à >A   å >A   ç >A
    DATA 136,69,137,69,138,69,139,73,140,73,141,73,142,65,143,65
    '     ê >E   ë >E   è >E   ï >I   î >I   ì >I   Ä >A   Å >A
    DATA 144,69,145,65,146,65,147,79,148,79,149,79,150,85,151,85
    '     É >E   æ >A   Æ >A   ô >O   ö >O   ò >O   û >U   ù >U
    DATA 152,121,153,79,154,85,155,67,158,83,160,65,161,73,162,79
    '     ÿ >Y    Ö >O   Ü >U   ¢ >C   ß >S   á >A   í >I   ó >O
    DATA 163,85,164,78,165,78,166,65,167,79,176,65,177,79,178,79
    '     ú >U   ñ >N   Ñ >N   ª >A   º >O   ã >A   õ >O   Ø >O
    DATA 179,79,180,79,181,79,182,65,183,65,184,79,192,121,193,121
    '     ø >O   œ >O   Œ >O   À >A   Ã >A   Õ >O   ? >Y    ? >Y
    DATA 225,83,0,0
    '     ? >S

 I  hope  your  printer-driver could  digest  all  these  special
characters.  Other  special  characters  are  treated  as  space-
characters.

 If you have done your homework,  you should now be able to write
a  clever alphabetical sorting-program yourself.  You  wanted  to
become  an expert,  didn't you?  Here are a few ideas to get  you
started:

     ' Sort string-array txt$() with index-array; ascii|() must
                                                            exist
     last=DIM?(txt$())-1           ! index of last element
     DIM temp$(last),index%(last)
     FOR i=0 TO last               ! copy strings to temporary
                                                            array
       temp$(i)=txt$(i)
     NEXT i
     FOR i=0 TO last               ! fill index-array with
                                                          numbers
       index%(i)=i
     NEXT i
     QSORT temp$() WITH ascii|(),last+1,index%()
     ERASE temp$()                 ! remove temporary string
                                                            array
     FOR i=0 TO last
       PRINT txt$(index%(i))       ! check result (for speedy
                                                         readers)
     NEXT i

 Do   you  still  remember  I  told  you  there  are  two   extra
possibilities?  Well,  the second extra possibility with  string-
arrays  is  the  use  of  'OFFSET o'  to  ignore  the  first  'o'
characters  during  sorting.  Suppose you have created  an  array
files$() with FILES and would like to sort the files by length:

     files$="A:\FILES.DAT"
     DIM files$(200)               ! create directory-array
     FILES "A:\*.*" TO files$      ! send directory to file on
                                                             disk
     OPEN "I",#1,files$
     RECALL #1,files$(),-1,x%      ! put directory in array
     CLOSE #1
     KILL files$                   ! throw temporary file away
     QSORT files$() OFFSET 13,n    ! sort array by file-length

 The  first  character (either a space or '*') and  the  filename
(the next 12 characters) are ignored during sorting.

Binary search

 The  fastest way to locate an element in a sorted array  is  the
binary search:

     ' Locate element in sorted word-array numb()
     first=0
     last=PRED(DIM?(numb()))
     WHILE first<last
       middle=DIV(ADD(first,last),2)
       IF element>numb(middle)
         first=SUCC(middle)
       ELSE
         last=middle
       ENDIF
     WEND
     ok!=(numb(first)=element)
     IF ok!
       index=first                 ! found the element at index
       PRINT index
     ELSE
       PRINT "not found"
     ENDIF

                     Procedures (CHAPTER.05)

Ascii_qsort and Init_ascii_array                         ASCIQSRT
 Sort  one-dimensional string-array  alphabetically,  with  byte-
array ascii|() taking care of special characters:
     @ascii_qsort(-1,array$())        ! -1 = entire array
 If the global array ascii|() didn't exist, it's first created by
the Procedure Init_ascii_array.  If you don't want to disturb the
original    string-array,    you    can   use    the    Procedure
String_index_qsort.

Bin_search_string                                         BIN_STR
 Find  a particular string in a sorted string-array with  'binary
search':
     element$="Han Kempen"
     @bin_search_string(TRUE,element$,names$(),index,found!)
     IF found!
       PRINT "String """;element$;""" has index ";index
     ELSE
       PRINT "String """;element$;""" not found in array"
     ENDIF
 If  the lowercase-switch is TRUE the Procedure searches  for  an
exact  fit,  so a string like "HAN KEMPEN" is ignored.  With  the
lowercase-switch FALSE,  all strings are converted to upper  case
before comparison, so "HAN KEMPEN" is now recognised as a hit. If
the   search   was  not   successful,   the   Procedure   returns
found!=FALSE.

Bin_search_word                                          BIN_WORD
 Find  a  particular  word in a sorted  word-array  with  'binary
search':
     element=25
     @bin_search_word(element,numbers&(),index,found!)
     IF found!
       PRINT "Element ";element;" has index ";index
     ELSE
       PRINT "Element ";element;" not found in array"
     ENDIF

Bubble_sort                                              BUBL_SRT
 Sort word-array with 'Bubble Sort':
     @bubble_sort(numbers&())
 Very slow. Only suitable for small arrays or for arrays that are
almost sorted already.

Comb_sort                                                COMB_SRT
 Sort word-array with 'Combsort':
     @comb_sort(numbers&())
 Simple and reasonably fast. This is a much improved Bubble Sort.

Insert_sort                                               INS_SRT
 Sort word-array with 'Insert Sort':
     @insert_sort(numbers&())

Iter_quick_sort                                          ITER_SRT
 Sort word-array with iterative 'Quick Sort':
     @iter_quick_sort(numbers&())
 Uses less memory than Quick_sort.

Quick_sort and Quick                                     QUIK_SRT
 Sort word-array with recursive 'Quick Sort':
     @quick_sort(numbers&())
 This Procedure uses the same algorithm as QSORT.  Because of the
recursion  (Procedure  calling itself repeatedly) you  could  run
into trouble with large arrays.  In that case Iter_quick_sort  is
more suitable.

Selection_sort                                            SEL_SRT
 Sort word-array with 'Selection Sort':
     @selection_sort(numbers&())

Shell_sort                                               SHEL_SRT
 Sort word-array with 'Shell Sort':
     @shell_sort(numbers&())
 This Procedure uses the same algorithm as SSORT.

String_index_qsort and Init_ascii_array                  STR_INDX
 Use an index-array to sort a string-array:
     @string_index_qsort(TRUE,name$(),index%())
     FOR i=0 TO DIM?(name$())-1
       PRINT name$(index%(i))
     NEXT i
 The string-array itself is not sorted.  The index-numbers of the
sorted array are returned in the array index%().  If the flag  is
TRUE,  the global array ascii|() is used to take care of  special
characters (Procedure Init_ascii_array is called). If the flag is
FALSE,  special characters are ignored and lower case  characters
(ASCII-values  97-122)  are not treated the same  as  upper  case
characters (ASCII-values 65-90).