5. SORT 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 firstnumb(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 (page 5-3) 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 (page 5-5) 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 (page 5-5) 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 (page 5-1) 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 (page 5-1) 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 (page 5-4) 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).