index 7d30242..d914135 100644 (file)
@@ -1,4 +1,4 @@
-@node Searching and Sorting, Input/Output Overview, Locales, Top
+@node Searching and Sorting, Pattern Matching, Locales, Top
@chapter Searching and Sorting

This chapter describes functions for searching and sorting arrays of
@@ -8,8 +8,9 @@ and the total number of elements.

* Comparison Functions::        Defining how to compare two objects.
-                               Since the sort and search facilities are
-                               general, you have to specify the ordering.
+                                Since the sort and search facilities
+                                 are general, you have to specify the
+                                 ordering.
* Array Search Function::       The @code{bsearch} function.
* Array Sort Function::         The @code{qsort} function.
* Search/Sort Example::         An example program.
@@ -33,28 +34,23 @@ is ``greater''.
Here is an example of a comparison function which works with an array of
numbers of type @code{double}:

-@example
+@smallexample
int
compare_doubles (const double *a, const double *b)
@{
-  double temp = *a - *b;
-  if (temp > 0)
-    return 1;
-  else if (temp < 0)
-    return -1;
-  else
-    return 0;
+  return (int) (*a - *b);
@}
-@end example
+@end smallexample

The header file @file{stdlib.h} defines a name for the data type of
-comparison functions.  This is a GNU extension and thus defined only if
-you request the GNU extensions.
+comparison functions.  This type is a GNU extension.

+@comment stdlib.h
+@comment GNU
@tindex comparison_fn_t
-@example
+@smallexample
int comparison_fn_t (const void *, const void *);
-@end example
+@end smallexample

@node Array Search Function, Array Sort Function, Comparison Functions, Searching and Sorting
@section Array Search Function
@@ -72,7 +68,7 @@ the header file @file{stdlib.h}.
@deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
The @code{bsearch} function searches the sorted array @var{array} for an object
that is equivalent to @var{key}.  The array contains @var{count} elements,
-each of which is of size @var{size}.
+each of which is of size @var{size} bytes.

The @var{compare} function is used to perform the comparison.  This
function is called with two pointer arguments and should return an
@@ -86,7 +82,7 @@ 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.
+using the binary search algorithm.
@end deftypefun

@node Array Sort Function, Search/Sort Example, Array Search Function, Searching and Sorting
@@ -106,14 +102,14 @@ To sort an array using an arbitrary comparison function, use the
The @var{qsort} function sorts the array @var{array}.  The array contains
@var{count} elements, each of which is of size @var{size}.

-The @var{compare} function is used to compare 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
+The @var{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.

@cindex stable sorting
-@strong{Warning:} if two objects compare as equal, their order after
+@strong{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
@@ -122,22 +118,24 @@ 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 (@pxref{Comparison
Functions}):

-@example
+@smallexample
@{
double *array;
int size;
@dots{}
qsort (array, size, sizeof (double), compare_doubles);
@}
-@end example
+@end smallexample

The @code{qsort} function derives its name from the fact that it was
-originally implemented using the algorithm ``quick sort''.
+originally implemented using the ``quick sort'' algorithm.
@end deftypefun

@node Search/Sort Example,  , Array Sort Function, Searching and Sorting
@@ -149,14 +147,30 @@ by comparing their @code{name} fields with the @code{strcmp} function.
Then, we can look up individual objects based on their names.

@comment This example is dedicated to the memory of Jim Henson.  RIP.
-@example
+@smallexample
@include search.c.texi
-@end example
+@end smallexample

@cindex Kermit the frog
The output from this program looks like:

-@example
+@smallexample
+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
+Zoot, the human
+Dr. Bunsen Honeydew, the human
+Beaker, the human
+Swedish Chef, the human
+
Animal, the animal
Beaker, the human
Camilla, the chicken
@@ -173,10 +187,9 @@ Swedish Chef, the human
Sweetums, the monster
Zoot, the human

-
Kermit, the frog
Gonzo, the whatever
Couldn't find Janice.
-@end example
+@end smallexample