SERCHING AND SORTING

SEARCHING AND SORTING




The stdlib.h provides 2 useful functions to perform general searching and

sorting of data on any type. In fact we have already introduced the qsort()

function.


For completeness we list the prototype again here but refer the reader to the

previous Chapter for an example.


The qsort standard library function is very useful function that is designed

to sort an array by a key value of any type into ascending order, as long as

the elements of the array are of fixed type.
qsort is prototyped (in stdlib.h):

VOID QSORT(VOID *BASE, SIZE_T NUM_ELEMENTS, SIZE_T ELEMENT_SIZE,

INT (*COMPARE)(VOID CONST *, VOID CONST *));

Similarly, there is a binary search function, bsearch() which is prototyped

(in stdlib.h) as:

VOID *BSEARCH(CONST VOID *KEY, CONST VOID *BASE, SIZE_T NEL,

SIZE_T SIZE, INT (*COMPARE)(CONST VOID *, CONST VOID *));

Using the same Record structure and record_compare function as the qsort()

example.

TYPEDEF STRUCT {
INT KEY;
STRUCT

OTHER_DATA;
} RECORD;

INT RECORD\_COMPARE(VOID CONST *A, VOID CONST *A)
{ RETURN ( ((RECORD *)A)->KEY - ((RECORD *)B)->KEY );
}

Also, Assuming that we have an array of array_length Records suitably filled

with date we can call bsearch() like this:



Record key;


RECORD *ANS;


KEY.KEY = 3; /* INDEX VALUE TO BE SEARCHED FOR */


ANS = BSEARCH(&KEY, ARRAY, ARRAYLENGTH, SIZEOF(RECORD), RECORD_COMPARE);




The function bsearch() return a pointer to the field whose key filed is filled

with the matched value of NULL if no match found.




Note



That the type of the key argument must be the same as the array elements

(Record above), even though only the key.key element is required to be set.