NAME    [Toc]    [Back]

     radixsort, sradixsort - radix sort

SYNOPSIS    [Toc]    [Back]

     #include <limits.h>
     #include <stdlib.h>

     int
     radixsort(const  u_char  **base,  int  nmemb,  const  u_char
*table,
             u_int endbyte);

     int
     sradixsort(const  u_char  **base,  int  nmemb,  const u_char
*table,
             u_int endbyte);

DESCRIPTION    [Toc]    [Back]

     The radixsort() and sradixsort() functions  are  implementations of radix
     sort.

     These  functions  sort  an  array  of nmemb pointers to byte
strings.  The
     initial member is referenced by base.  The byte strings  may
contain any
     values; the end of each string is denoted by the user-specified value
     endbyte.

     Applications may specify a sort order by providing the table
argument.
     If  non-null, table must reference an array of UCHAR_MAX + 1
bytes which
     contains the sort weight of each possible byte  value.   The
end-of-string
     byte must have a sort weight of 0 or 255 (for sorting in reverse order).
     More than one byte may have the same sort weight.  The table
argument is
     useful for applications which wish to sort different characters equally,
     for example, providing a table with the same weights for A-Z
as for a-z
     will  result  in a case-insensitive sort.  If table is NULL,
the contents
     of the array are sorted in ascending order according to  the
ASCII order
     of the byte strings they reference and endbyte has a sorting
weight of 0.

     The sradixsort() function is stable; that is,  if  two  elements compare as
     equal,  their  order  in the sorted array is unchanged.  The
sradixsort()
     function uses additional memory  sufficient  to  hold  nmemb
pointers.

     The  radixsort()  function  is not stable, but uses no additional memory.

     These functions are variants of most-significant-byte  radix
sorting; in
     particular,  see D.E. Knuth's Algorithm R and section 5.2.5,
exercise 10.
     They take linear time relative to the number of bytes in the
strings.

RETURN VALUES    [Toc]    [Back]

     Upon  successful completion 0 is returned.  Otherwise, -1 is
returned and
     the global variable errno is set to indicate the error.

ERRORS    [Toc]    [Back]

     [EINVAL]      The value of the endbyte element of  table  is
not 0 or 255.

     Additionally,  the  sradixsort()  function  may fail and set
errno for any of
     the errors specified for the library routine malloc(3).

SEE ALSO    [Toc]    [Back]

     sort(1), qsort(3)

     Knuth, D.E., "Sorting and Searching", The  Art  of  Computer
Programming,
     Vol. 3, pp. 170-178, 1968.

     Paige,  R., "Three Partition Refinement Algorithms", SIAM J.
Comput., No.
     6, Vol. 16, 1987.

     McIlroy, P., "Computing Systems",  Engineering  Radix  Sort,
Vol. 6:1, pp.
     5-27, 1993.

HISTORY    [Toc]    [Back]

     The radixsort() function first appeared in 4.4BSD.

OpenBSD      3.6                         January     27,     1994