index 3ffcb4b..abb93bb 100644 (file)
@@ -1,5 +1,5 @@
-@node Searching and Sorting, Pattern Matching, Locales, Top
-@chapter Searching and Sorting
+@node Searching and Sorting, Pattern Matching, Message Translation, Top
+@chapter Searching and Sorting

This chapter describes functions for searching and sorting arrays of
arbitrary objects.  You pass the appropriate comparison function to be
@@ -10,7 +10,7 @@ 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.
+                                 ordering.
* Array Search Function::       The @code{bsearch} function.
* Array Sort Function::         The @code{qsort} function.
* Search/Sort Example::         An example program.
@@ -34,30 +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
@@ -71,11 +64,11 @@ the header file @file{stdlib.h}.
@pindex stdlib.h

@comment stdlib.h
-@comment ANSI
+@comment ISO
@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
@@ -104,7 +97,7 @@ To sort an array using an arbitrary comparison function, use the
@pindex stdlib.h

@comment stdlib.h
-@comment ANSI
+@comment ISO
@deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
The @var{qsort} function sorts the array @var{array}.  The array contains
@var{count} elements, each of which is of size @var{size}.
@@ -125,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
@@ -152,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
@@ -176,10 +187,7 @@ Swedish Chef, the human
Sweetums, the monster
Zoot, the human

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