home *** CD-ROM | disk | FTP | other *** search
/ ProfitPress Mega CDROM2 …eeware (MSDOS)(1992)(Eng) / ProfitPress-MegaCDROM2.B6I / PROG / PASCAL / MISCTI10.ZIP / TI398.ASC < prev    next >
Encoding:
Text File  |  1988-05-02  |  3.3 KB  |  121 lines
  1.  
  2. qsort is an implementation of the Quicksort algorithm and
  3. requires four parameters:  the array to sort, the length of the
  4. array, the width of the array, and a comparison function.
  5.  
  6. qsort 's length and width parameters are fairly straightforward. 
  7. If you are sorting an array declared as:
  8.  
  9.             int array[100];
  10.  
  11. the length of the array is 100 and the width of the array is
  12. "sizeof(int)".   Generally, the length and width of any array can
  13. be expressed as:  "sizeof(array)/sizeof(array[0])" (the size of
  14. array divided by the size of the first element of array), and
  15. "sizeof(array[0])" (the size of the first element of array)
  16. respectively.
  17.  
  18. The fourth parameter (the comparison routine) usually causes the
  19. most trouble.  The reference guide states that the fourth
  20. parameter is a pointer to a function.  This means that you must
  21. give the name of a routine as the fourth parameter; you must
  22. supply this routine yourself.
  23.  
  24. qsort will call your routine to do all comparisons.  Pointers
  25. will be passed to the array elements which are to be compared. 
  26. You do not have to be concerned how this is done, qsort will
  27. handle this for you.  Your routine must return an integer, the
  28. value of which will be:
  29.  
  30.   positive   -  if the first element is greater than the second.
  31.  
  32.           0  -  if the elements are equal.
  33.  
  34.   negative   -  if the second element is greater than the first.
  35.  
  36. To sort the above array in ascending order, the routine is:
  37.  
  38. int fcmp(int *num1, int *num2)
  39. {
  40.     return (*num1 - *num2);
  41. }
  42.  
  43. qsort can also sort arrays of structures.  If the array was
  44. defined:
  45.  
  46. struct address
  47. {
  48.     char LastName[16];
  49.     char FirstName[11];
  50.     char Street[30];
  51.     char City[21];
  52.     char State[3];
  53.     char Zip[6];
  54. } AddressBook[100];
  55.  
  56. To sort "AddressBook" on "LastName" the fcmp routine would be:
  57.  
  58. int fcmp(struct address *first, struct address *second)
  59. {
  60.     return (strcmp(first->LastName,second->LastName));
  61. }
  62.  
  63. To sort the same array on "Zip" in the above routine, simply
  64. change "LastName" to "Zip".  The call to qsort for both examples
  65. would look like:
  66.  
  67.   qsort(AddressBook, sizeof(AddressBook)/sizeof(AddressBook[0]),
  68.          sizeof(AddressBook[0]), fcmp);
  69.  
  70. The best way to put this all together is a sample program.
  71.  
  72. /* The program will generate 100 random numbers.  Store them
  73.  * in an array.  Print them out.  Call qsort to sort them
  74.  * and print them out again.
  75.  */
  76.  
  77. #include <stdio.h>
  78. #include <stdlib.h>
  79. #include <time.h>
  80.  
  81. #define ARRAYLEN 100
  82.  
  83. int array[ARRAYLEN];       /* Array to sort */
  84. /* Comparison routine passed to and used by qsort() */
  85. int fcmp(int *num1, int *num2)
  86. {
  87.     return (*num1 - *num2);
  88. }
  89.  
  90. main()
  91. {
  92.    long along;
  93.    int i;
  94.  
  95.    /* Seed the random number generator */
  96.    srand((unsigned) time(&along));
  97.    for (i=0; i<ARRAYLEN; i++)
  98.        array[i] = rand() % ARRAYLEN;
  99.  
  100.    /* Print the random array */
  101.    printf("\nOriginal array\n");
  102.    for (i=0; i<ARRAYLEN; i++)
  103.    {
  104.        printf("%4d ",array[i]);
  105.        if ( !((i+1) % 15) )
  106.            putchar('\n');
  107.    }
  108.  
  109.    /* Call qsort() */
  110.   qsort(array,sizeof(array)/sizeof(*array),sizeof(*array),fcmp);
  111.  
  112.    /* Print the sorted array */
  113.    printf("\n\nSorted array\n");
  114.    for (i=0; i<ARRAYLEN; i++)
  115.    {
  116.        printf("%4d ",array[i]);
  117.        if ( !((i+1) % 15) )
  118.            putchar('\n');
  119.    }
  120. }
  121.