home *** CD-ROM | disk | FTP | other *** search
/ Microsoft Programmer's Library 1.3 / Microsoft-Programers-Library-v1.3.iso / sampcode / c / other / learn / sort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-10-19  |  3.1 KB  |  103 lines
  1. /* SORT.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.  
  83. /* Compare and return greater than (1), less than (-1), or equal to (0).
  84.  * This function is called by qsort and bsearch.
  85.  */
  86. unsigned cmpgle( unsigned *arg1, unsigned *arg2 )
  87. {
  88.     if( *arg1 > *arg2 )
  89.         return 1;
  90.     else if( *arg1 < *arg2 )
  91.         return -1;
  92.     else
  93.         return 0;
  94. }
  95.  
  96. /* Compare and return equal (1) or not equal (0). This function is
  97.  * called by lfind and lsearch.
  98.  */
  99. unsigned cmpe( unsigned *arg1, unsigned *arg2 )
  100. {
  101.     return !( *arg1 == *arg2 );
  102. }
  103.