home *** CD-ROM | disk | FTP | other *** search
/ Microsoft Programmer's Library 1.3 / Microsoft-Programers-Library-v1.3.iso / sampcode / c / other / learn / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-10-25  |  3.1 KB  |  102 lines
  1. /* QSORT.C illustates randomizing, sorting, and searching. Functions
  2.  * illustrated include:
  3.  *      srand           rand            qsort
  4.  *      lfind           lsearch         bsearch
  5.  *
  6.  * The lsearch function is not specifically shown in the program, but
  7.  * its use is the same as lfind except that if it does not find the
  8.  * element, it inserts it at the end of the array rather than failing.
  9.  */
  10.  
  11. #include <search.h>
  12. #include <stdlib.h>
  13. #include <string.h>
  14. #include <stdio.h>
  15. #include <time.h>
  16.  
  17. #define  ASIZE 1000
  18. unsigned array[ASIZE];
  19.  
  20. /* Macro to get a random integer within a specified range */
  21. #define getrandom( min, max ) ((rand() % (int)((max) - (min))) + (min) + 1)
  22.  
  23. /* Must be declared before call */
  24. unsigned cmpgle( unsigned *arg1, unsigned *arg2 );
  25. unsigned cmpe( unsigned *arg1, unsigned *arg2 );
  26.  
  27. main()
  28. {
  29.     unsigned i, *result, elements = ASIZE, key = ASIZE / 2;
  30.  
  31.     /* Seed the random number generator with current time. */
  32.     srand( (unsigned)time( 0L ) );
  33.  
  34.     /* Build a random array of integers. */
  35.     printf( "Randomizing . . .\n" );
  36.     for( i = 0; i < ASIZE; i++ )
  37.         array[i] = getrandom( 1, ASIZE );
  38.  
  39.     /* Show every tenth element. */
  40.     printf( "Printing every tenth element . . .\n" );
  41.     for( i = 9; i < ASIZE; i += 10 )
  42.     {
  43.         printf( "%5u", array[i] );
  44.         if( !(i % 15) )
  45.             printf( "\n" );
  46.     }
  47.  
  48.     /* Find element using linear search. */
  49.     printf( "\nDoing linear search . . .\n" );
  50.     result = (unsigned *)lfind( (char *)&key, (char *)array, &elements,
  51.                                 sizeof( unsigned ), cmpe);
  52.     if( result == NULL )
  53.         printf( "  Value %u not found\n", key );
  54.     else
  55.         printf( "  Value %u found in element %u\n", key, result - array + 1);
  56.  
  57.     /* Sort array using Quicksort algorithm. */
  58.     printf( "Sorting . . .\n" );
  59.     qsort( (void *)array, (size_t)ASIZE, sizeof( int ), cmpgle );
  60.  
  61.     /* Show every tenth element. */
  62.     printf( "Printing every tenth element . . .\n" );
  63.     for( i = 9; i < ASIZE; i += 10 )
  64.     {
  65.         printf( "%5u", array[i] );
  66.         if( !(i % 15) )
  67.             printf( "\n" );
  68.     }
  69.  
  70.     /* Find element using binary search. Note that the array must
  71.      * be previously sorted before using binary search.
  72.      */
  73.     printf( "\nDoing binary search . . .\n" );
  74.     result = (unsigned *)bsearch( (char *)&key, (char *)array, elements,
  75.                                   sizeof( unsigned ), cmpgle);
  76.     if( result == NULL )
  77.         printf( "  Value %u not found\n", key );
  78.     else
  79.         printf( "  Value %u found in element %u\n", key, result - array + 1 );
  80. }
  81.  
  82. /* Compare and return greater than (1), less than (-1), or equal to (0).
  83.  * This function is called by qsort and bsearch.
  84.  */
  85. unsigned cmpgle( unsigned *arg1, unsigned *arg2 )
  86. {
  87.     if( *arg1 > *arg2 )
  88.         return 1;
  89.     else if( *arg1 < *arg2 )
  90.         return -1;
  91.     else
  92.         return 0;
  93. }
  94.  
  95. /* Compare and return equal (1) or not equal (0). This function is
  96.  * called by lfind and lsearch.
  97.  */
  98. unsigned cmpe( unsigned *arg1, unsigned *arg2 )
  99. {
  100.     return !( *arg1 == *arg2 );
  101. }
  102.