This chapter describes functions for searching and sorting arrays of arbitrary objects. You pass the appropriate comparison function to be applied as an argument, along with the size of the objects in the array and the total number of elements.
bsearch function.
qsort function.
In order to use the sorted array library functions, you have to describe how to compare the elements of the array.
To do this, you supply a comparison function to compare two elements of
the array. The library will call this function, passing as arguments
pointers to two array elements to be compared. Your comparison function
should return a value the way strcmp (see section 5.5 String/Array Comparison) does: negative if the first argument is "less" than the
second, zero if they are "equal", and positive if the first argument
is "greater".
Here is an example of a comparison function which works with an array of
numbers of type double:
int
compare_doubles (const double *a, const double *b)
{
return (int) (*a - *b);
}
The header file `stdlib.h' defines a name for the data type of comparison functions. This type is a GNU extension.
int comparison_fn_t (const void *, const void *);
To search a sorted array for an element matching the key, use the
bsearch function. The prototype for this function is in
the header file `stdlib.h'.
bsearch function searches the sorted array array for an object
that is equivalent to key. The array contains count elements,
each of which is of size size bytes.
The compare function is used to perform the comparison. This function is called with two pointer arguments and should return an integer less than, equal to, or greater than zero corresponding to whether its first argument is considered less than, equal to, or greater than its second argument. The elements of the array must already be sorted in ascending order according to this comparison function.
The return value is a pointer to the matching array element, or a null pointer if no match is found. If the array contains more than one element that matches, the one that is returned is unspecified.
This function derives its name from the fact that it is implemented using the binary search algorithm.
To sort an array using an arbitrary comparison function, use the
qsort function. The prototype for this function is in
`stdlib.h'.
The compare function is used to perform the comparison on the array elements. This function is called with two pointer arguments and should return an integer less than, equal to, or greater than zero corresponding to whether its first argument is considered less than, equal to, or greater than its second argument.
Warning: If two objects compare as equal, their order after sorting is unpredictable. That is to say, the sorting is not stable. This can make a difference when the comparison considers only part of the elements. Two elements with the same sort key may differ in other respects.
If you want the effect of a stable sort, you can get this result by writing the comparison function so that, lacking other reason distinguish between two elements, it compares them by their addresses. Note that doing this may make the sorting algorithm less efficient, so do it only if necessary.
Here is a simple example of sorting an array of doubles in numerical order, using the comparison function defined above (see section 15.1 Defining the Comparison Function):
{
double *array;
int size;
...
qsort (array, size, sizeof (double), compare_doubles);
}
The qsort function derives its name from the fact that it was
originally implemented using the "quick sort" algorithm.
Here is an example showing the use of qsort and bsearch
with an array of structures. The objects in the array are sorted
by comparing their name fields with the strcmp function.
Then, we can look up individual objects based on their names.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
/* Define an array of critters to sort. */
struct critter
{
const char *name;
const char *species;
};
struct critter muppets[] =
{
{"Kermit", "frog"},
{"Piggy", "pig"},
{"Gonzo", "whatever"},
{"Fozzie", "bear"},
{"Sam", "eagle"},
{"Robin", "frog"},
{"Animal", "animal"},
{"Camilla", "chicken"},
{"Sweetums", "monster"},
{"Dr. Strangepork", "pig"},
{"Link Hogthrob", "pig"},
{"Zoot", "human"},
{"Dr. Bunsen Honeydew", "human"},
{"Beaker", "human"},
{"Swedish Chef", "human"}
};
int count = sizeof (muppets) / sizeof (struct critter);
/* This is the comparison function used for sorting and searching. */
int
critter_cmp (const struct critter *c1, const struct critter *c2)
{
return strcmp (c1->name, c2->name);
}
/* Print information about a critter. */
void
print_critter (const struct critter *c)
{
printf ("%s, the %s\n", c->name, c->species);
}
/* Do the lookup into the sorted array. */
void
find_critter (const char *name)
{
struct critter target, *result;
target.name = name;
result = bsearch (&target, muppets, count, sizeof (struct critter),
critter_cmp);
if (result)
print_critter (result);
else
printf ("Couldn't find %s.\n", name);
}
/* Main program. */
int
main (void)
{
int i;
for (i = 0; i < count; i++)
print_critter (&muppets[i]);
printf ("\n");
qsort (muppets, count, sizeof (struct critter), critter_cmp);
for (i = 0; i < count; i++)
print_critter (&muppets[i]);
printf ("\n");
find_critter ("Kermit");
find_critter ("Gonzo");
find_critter ("Janice");
return 0;
}
The output from this program looks like:
Kermit, the frog Piggy, the pig Gonzo, the whatever Fozzie, the bear Sam, the eagle Robin, the frog Animal, the animal Camilla, the chicken Sweetums, the monster Dr. Strangepork, the pig Link Hogthrob, the pig Zoot, the human Dr. Bunsen Honeydew, the human Beaker, the human Swedish Chef, the human Animal, the animal Beaker, the human Camilla, the chicken Dr. Bunsen Honeydew, the human Dr. Strangepork, the pig Fozzie, the bear Gonzo, the whatever Kermit, the frog Link Hogthrob, the pig Piggy, the pig Robin, the frog Sam, the eagle Swedish Chef, the human Sweetums, the monster Zoot, the human Kermit, the frog Gonzo, the whatever Couldn't find Janice.
Go to the first, previous, next, last section, table of contents.