home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 4 / DATAFILE_PDCD4.iso / utilities / utilsd / evntshell / Docs / Misc < prev    next >
Encoding:
Text File  |  1994-01-07  |  4.6 KB  |  164 lines
  1. PROCshell_QuickSort()
  2. Params =>
  3.          str comparison function
  4.          str swap function
  5.          bool ascending flag, non 0 for ascending
  6.               sort, 0 for descending sort
  7.          int minimum element number to sort
  8.          int maximum element number to sort
  9.  
  10. The QuickSort routine uses a fast sorting technique
  11. which is capable of sorting any type of data. An
  12. example of the speed is that 1000 random integers
  13. can be sorted in around 15 seconds on an ARM3
  14. machine.
  15.  
  16. Comparision FN (QuickSort)
  17. Params =>
  18.          int first  element nr
  19.          int second element nr
  20.  
  21.        <=
  22.          bool TRUE if value of first element
  23.               is less than the second,
  24.               otherwise FALSE
  25.  
  26. This function returns TRUE or FALSE depending
  27. on the outcome of the comparison. Exactly what
  28. is compared is up to you!
  29.  
  30. The function name must start with a '_'
  31. character if the program is to be compressed.
  32.  
  33. Swap FN (QuickSort)
  34. Params =>
  35.          int first  element nr
  36.          int second element nr
  37.  
  38.        <=
  39.          int junk (ignore)
  40.  
  41. This function swaps element 1 with element
  42. 2.
  43.  
  44. The function name must start with a '_'
  45. character if the program is to be compressed.
  46.  
  47. Example code (QuickSort)
  48. Assume a 100 element string array name$(), each element
  49. containing a list of names which must be sorted into
  50. alphabetic order. This can be achieved with:
  51.  
  52. REM Rest of code....
  53. PROCshell_QuickSort("_QS_comp","_QS_swap",1,0,100)
  54. REM More code..
  55.  
  56. DEF FN_QS_comp(el1%,el2%)
  57. IF VAL(name$(el1%)) < VAL(name$(el2%)) THEN = TRUE ELSE = FALSE
  58. :
  59. DEF FN_QS_swap(el1%,el2%)
  60. LOCAL temp$
  61. temp$ = name$(el1%)
  62. name$(el1%) = name$(el2%)
  63. name$(el2%) = temp$
  64. =0
  65.  
  66. The complexity of FN_QS_comp and FN_QS_swap is completely up to
  67. you (wildcards could be allowed for example). By this means any
  68. set of data can be sorted.
  69.  
  70. --------------------------------------------------------
  71.  
  72. FNshell_BinarySearch()
  73. Params =>
  74.          str search term
  75.          str get term function
  76.          str comparison function
  77.          int minimum element number
  78.          int maximum element number
  79.  
  80.        <=
  81.          int element number of first match
  82.              found (first element is 1) or
  83.              -1 if match not found
  84.  
  85. The Binary Search technique is a powerful way of
  86. quickly searching a set of sorted data. The way in
  87. which it has been implemented for EvntShell makes
  88. it even more useful in that any set of data can be
  89. searched by the same routine.
  90.  
  91. The key to this are the two routines called during
  92. the search to get an element of data and to compare
  93. one element to another.
  94.  
  95. Search term (BinarySearch)
  96. The search term is the string which will be searched
  97. for during the binary search. Note that a string must
  98. be passed to the search routine, numbers must be
  99. converted first using STR$.
  100.  
  101. Get Term FN (BinarySearch)
  102. Params =>
  103.          int element number to fetch
  104.  
  105.        <=
  106.          str value of element number
  107.  
  108. This function returns a string representing
  109. the value of the specified element.
  110.  
  111. The function name must start with a '_'
  112. character if the program is to be compressed.
  113.  
  114. Comparision FN (BinarySearch)
  115. Params =>
  116.          str term 1
  117.          str term 2
  118.  
  119.        <=
  120.          bool TRUE if term 1 is less than
  121.               term 2, otherwise FALSE
  122.  
  123. This function returns TRUE or FALSE depending
  124. on the outcome of the comparison. Exactly what
  125. is compared is up to you!
  126.  
  127. The function name must start with a '_'
  128. character if the program is to be compressed.
  129.  
  130. The Binary Search Technique
  131. Given a set of sorted data, a check is first made halfway
  132. through the list. If the searched for data is 'greater than'
  133. this value then the next check is made half way between the
  134. first point and the end of the list, otherwise the next check
  135. is made half way between the first check and the start of the
  136. list.
  137.  
  138. This continues (eliminating half the remaining data with each
  139. check) until the data is found, or the list can contain no
  140. more matches.
  141.  
  142. By this means very large amounts of data can be searched very
  143. quickly indeed.
  144.  
  145. Example code (BinarySearch)
  146. Assume a 100 element string array array$(), each element
  147. containing a list of names sorted into alphabetic order.
  148. The search can be carried out with:
  149.  
  150. result%=FNshell_BinarySearch("Fred","_GetTerm","_Comp",0,99)
  151. REM rest of code....
  152.  
  153. DEF FN_GetTerm(nr%)
  154. =array$(nr%)
  155. :
  156. DEF FN_Comp(term1$,term2$)
  157. IF term1$ < term2$ THEN = TRUE ELSE =FALSE
  158.  
  159. result% contains -1 if 'Fred' is not present in array$, or
  160. the element number if it is. The complexity of FN_GetTerm
  161. and FN_Comp is completely up to you (wildcards could be
  162. allowed for example). By this means any set of sorted data
  163. can be searched - simply define the 'get term' and 'comparision'
  164. functions to suit.