◄Up► ◄Contents► ◄Index► ◄Back►
─────Run-Time Library───────────────────────────────────────────────────────
 
/* QSORT.C illustates randomizing, sorting, and searching. Functions
 * illustrated include:
 *      srand           rand            qsort
 *      _lfind          _lsearch        bsearch
 *
 * The _lsearch function is not specifically shown in the program, but
 * its use is the same as _lfind except that if it does not find the
 * element; it inserts it at the end of the array rather than failing.
 */
 
#include <search.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <time.h>
 
#define  ASIZE 1000
unsigned array[ASIZE];
 
/* Macro to get a random integer within a specified range */
#define getrandom( min, max ) ((rand() % (int)(((max)+1) - (min))) + (min))
 
/* Must be declared before call */
int __cdecl cmpgle( const void *elem1, const void *elem2 );
int __cdecl cmpe( const void *key, const void *tableentry );
 
void main()
{
    unsigned i, *result, elements = ASIZE, key = ASIZE / 2;
 
    /* Seed the random number generator with current time. */
    srand( (unsigned)time( NULL ) );
 
    /* Build a random array of integers. */
    printf( "Randomizing . . .\n" );
    for( i = 0; i < ASIZE; i++ )
        array[i] = getrandom( 1, ASIZE );
 
    /* Show every tenth element. */
    printf( "Printing every tenth element . . .\n" );
    for( i = 9; i < ASIZE; i += 10 )
    {
        printf( "%5u", array[i] );
        if( !(i % 15) )
            printf( "\n" );
    }
 
    /* Find element using linear search. */
    printf( "\nDoing linear search . . .\n" );
    result = (unsigned *)_lfind( &key, array, &elements,
                                 sizeof( unsigned ), cmpe );
 
    if( result == NULL )
        printf( "  Value %u not found\n", key );
    else
        printf( "  Value %u found in element %u\n", key, result - array + 1);
 
    /* Sort array using Quicksort algorithm. */
    printf( "Sorting . . .\n" );
    qsort( array, ASIZE, sizeof( int ), cmpgle );
 
    /* Show every tenth element. */
    printf( "Printing every tenth element . . .\n" );
    for( i = 9; i < ASIZE; i += 10 )
    {
        printf( "%5u", array[i] );
        if( !(i % 15) )
            printf( "\n" );
    }
 
    /* Find element using binary search. Note that the array must
     * be previously sorted before using binary search.
     */
    printf( "\nDoing binary search . . .\n" );
    result = (unsigned *)bsearch( &key, array, elements,
                                  sizeof( unsigned ), cmpgle );
    if( result == NULL )
        printf( "  Value %u not found\n", key );
    else
        printf( "  Value %u found in element %u\n",
                key, result - array + 1 );
}
 
/* Compares and returns greater than (1), less than (-1), or equal to (0).
 * This function is called by qsort and bsearch. When used with qsort the
 * order of entries is unimportant. When used with bsearch, elem1 is the
 * key to be found, and elem2 is the current table entry.
 */
int __cdecl cmpgle( const void *elem1, const void *elem2 )
{
    if( *(unsigned *)elem1 > *(unsigned *)elem2 )
        return 1;
    else if( *(unsigned *)elem1 < *(unsigned *)elem2 )
        return -1;
    else
        return 0;
}
 
/* Compares and returns equal (1) or not equal (0). This function is
 * called by _lfind and _lsearch.
 */
int __cdecl cmpe( const void *key, const void *tableentry )
{
    return !( *(unsigned *)key == *(unsigned *)tableentry );
}
                                    -♦-