★ APPLICATIONS ★ DIVERS ★ Shelling out for strings ★ |
Machine Code Shell Sort (Computing with the Amstrad) | Applications Divers |
Sort character arrays in a flash with MIKE MEE's clever utility AFTER reading the excellent series in the June and July issues on sorting data, you may be frustrated by the speed - or lack of it - at which Basic can deal with such tasks. When a large amount of information is involved, it's definitely a case of patience being a virtue. Fortunately, with my utility you can throw said virtue out the window. Anyone who has, or is developing, a Basic program that stores and manipulates string array data - for instance a mailing list, club membership register, or accounting system - will find Program I invaluable. It installs some machine code which is capable of sorting a string array into ascending or descending order. It also gives a quick - literally -demonstration of its power. After running the program, the syntax for using the facility is: CALL sort,sort,ord,@array$(first),last-firstThat may look complicated, but in practice it is quite straightforward. Say you have a string array called fred$. It has 100 elements numbered 0-99, and you want them in descending order. Your program will have incorporated Program I, so the variable sort will already be set up with the correct value - the address of the sort routine. If you are sure what you are doing, you can alter the value of sort in the The variable ord tells the routine whether it has to sort in ascending or descending order - 56 or 48 respectively. first and last are the first and last elements of the array to be included in the sort. In this case they will be 0 and 99, but you can work on any subsection of the array you want: CALL sort,sort,48,@fred$(0),99One point to note is that value of last must be greater or equal than two, and first must be less than or equal to last-2. This program will only work on string arrays, so you must convert numeric data to string format using the STR$ command. And that's all you need to use the utility, but for those interested in the nuts and bolts here is some background information. Sorting is one of the most common operations in applications programming, and a Three non-job specific methods were narrowed down as contenders, namely the quick, selection and shell sorts. Quick sort, as the name implies, is fast. However it was ruled out because it requires dynamic array space in which to store its partition pointers. Or more simply put, it needs two extra arrays for intermediate results, which in turn consumes precious memory. Selection sort was put aside due to the fact that the same number of compares and swaps is made if the list is random, or if only one element is out of order, therefore making it quite slow. Shell sort, however, is pretty fast for random lists and does not require extra arrays. As you will remember, shell sort works by applying half the array size as a gap, and successively comparing and swapping elements as necessary. The gap is halved with each repetition until finally adjacent elements are compared. At this stage the array is sorted. In general purpose Basic the algorithm looks like this: 10 first=0:last=100:gap=last:DIM array$(last) |
|
|