home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / QKSORT.ZIP / QKSORT.DOC next >
Encoding:
Text File  |  1990-02-14  |  5.1 KB  |  153 lines
  1. QKSORT Documentation
  2. --------------------
  3.  
  4. QKSORT is a small unit for Turbo Pascal 5.0 that implements two routines
  5. similar to ones found in the Turbo C library: qsort and bsearch.
  6.  
  7. qsort performs in-memory sorting of an array with the Quicksort algorithm.
  8. arrays of any type, up to a maximum of 32767 elements, may be sorted.
  9.  
  10. bsearch performs a binary search of an array.  The array must be in sorted
  11. order, and may be of any type, up to a maximum of 32767 elements.
  12.  
  13. As in the Turbo C functions, qsort and bsearch are "engines" which rely on
  14. a user-written comparison function to determine the proper sort sequence.
  15. This gives you tremendous flexibility, because you don't need a separate
  16. sort or search routine for each data structure.  Only the comparison
  17. function needs to change.
  18.  
  19.  
  20. Defining the comparison function
  21. --------------------------------
  22.  
  23. Your comparison function MUST be written with the following format:
  24.  
  25.    {$F+}                                { must be a far call }
  26.    function mycomp(var p1,p2) : integer;
  27.  
  28.    begin
  29.       ...
  30.       mycomp := ...
  31.    end;
  32.    {$F-}
  33.  
  34. You may use any function name you wish, but it MUST be a far function
  35. {$F+}, it MUST have two untyped var parameters (p1 and p2), and it MUST
  36. return an integer.
  37.  
  38. The comparison function must return an integer based on the sequence of the
  39. two records:
  40.  
  41.    <0  record p1 comes BEFORE record p2 in sequence
  42.     0  record p1 and record p2 are equivalent in terms of sequence
  43.    >0  record p1 comes AFTER record p2 in sequence
  44.  
  45.  
  46. Using qsort
  47. -----------
  48.  
  49. Usually, you will be sorting or searching on arrays of records.  Here is an
  50. example showing how a comparsion function would be written.  Suppose you
  51. have a mailing list that you want to sort in ascending order of last name:
  52.  
  53.    uses
  54.       qksort;
  55.  
  56.    type
  57.       mail_rec      = record            { mailing list record }
  58.                          id    : integer;         { ID number }
  59.                          lname : string[24];      { last name }
  60.                          fname : string[12];      { first name }
  61.                          .
  62.                          .  (additional fields in record)
  63.                          .
  64.                       end;
  65.  
  66.    var
  67.       mail_list     = array[0..100] of mail_rec;
  68.  
  69.  
  70.    function mail_comp(var p1,p2) : integer;
  71.  
  72.    { comparison function to sort mailing list in ascending order of
  73.      last name. }
  74.  
  75.    begin
  76.       if mail_rec(p1).lname < mail_rec(p2).lname then
  77.          mail_comp := -1
  78.       else if mail_rec(p1).lname > mail_rec(p2).lname then
  79.          mail_comp := 1
  80.       else
  81.          mail_comp := 0;
  82.    end;
  83.  
  84.  
  85. Notice the use of "mail_rec(p1)".  This typecasting is necessary so that
  86. Turbo can figure out the type of the variables being compared, since they
  87. are passed as untyped parameters.
  88.  
  89. Notice also that this function could easily be changed to sort on a
  90. different field, or to sort in descending order instead of ascending order.
  91.  
  92. Now, to actually sort the records, assuming the number of actual records
  93. in the array is in the variable numrec, the call is:
  94.  
  95.    qsort(mail_list,nr,sizeof(mail_rec),mail_comp);
  96.  
  97. You should always use the sizeof() function to pass the record size.  In
  98. that way, if you ever change the record structure, your sort call will
  99. not need to be modified.
  100.  
  101.  
  102. Using bsearch
  103. -------------
  104.  
  105. bsearch performs a binary search on a sorted array for a given key value.
  106. Note that the array must be sorted; otherwise bsearch will not work
  107. properly.
  108.  
  109. The call to bsearch is similar to the call to qsort, except that you need
  110. to specify the key value as the first parameter.  Using the example above,
  111. if you wanted to search for a key value stored in the variable k, the call
  112. would be:
  113.  
  114.    i := bsearch(k,mail_list,nr,sizeof(mail_list),mail_comp);
  115.  
  116. The function returns either a record number (starting at 0) if the key was
  117. found, or -1 if the key was not found.  (Note: this is different that the
  118. Turbo C function return of a pointer.)
  119.  
  120. IMPORTANT NOTE:  bsearch does not care what the type of the key value is.
  121. It is the responsibility of the comparison function to know that the SECOND
  122. parameter passed is the key value, while the first parameter is a record.
  123. This leaves you with two choices:
  124.  
  125. Method 1 is to pass a simple key value (a string in the example shown), in
  126. which case the comparison function must be aware that the two parameters
  127. being passed are of different types.
  128.  
  129. Method 2 is to pass an entire record of the same type as the array being
  130. searched.  This record only needs to have the key value set.  The advantage
  131. of method 2 is that you can use the same comparison function for both qsort
  132. and bsearch.
  133.  
  134. Using method 2 on the example above, the value k would have been defined
  135. as:
  136.  
  137.    var
  138.       k             : mail_rec;         { a single record }
  139.  
  140.    .
  141.    .
  142.    .
  143.  
  144.    k.lname := 'Schwartz';               { the key I'm looking for }
  145.    i := bsearch(k,mail_list,nr,sizeof(mail_list),mail_comp);
  146.  
  147.  
  148. Good luck with these routines.  I hope you find them useful.
  149.  
  150.    -- Bob Showalter
  151.       CompuServe ID 72220,466
  152.  
  153.