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