Important Notice

The pages on this site contain documentation for very old MS-DOS software, purely for historical purposes. If you're looking for up-to-date documentation, particularly for programming, you should not rely on the information found here, as it will be woefully out of date.

                                             ◄Up► ◄Contents► ◄Index► ◄Back►
────────────────────────────────────────────────────────────────────────────
 
/* 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 cmpgle( unsigned *elem1, unsigned *elem2 );
int cmpe( unsigned *key, unsigned *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( (char *)&key,
                                (char *)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( (void *)array, (size_t)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( (char *)&key, (char *)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 the current table entry.
 */
int cmpgle( unsigned *elem1, unsigned *elem2 )
{
    if( *elem1 > *elem2 )
        return 1;
    else if( *elem1 < *elem2 )
        return -1;
    else
        return 0;
}
 
/* Compares and returns equal (1) or not equal (0). This function is
 * called by lfind and lsearch.
 */
int cmpe( unsigned *key, unsigned *tableentry )
{
    return !( *key == *tableentry );
}