radixsort,
sradixsort
—
radix sort
#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);
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 userspecified value
endbyte.
Applications may specify a sort order by providing the
table argument. If nonnull,
table must reference an array of
UCHAR_MAX
+ 1 bytes which contains the sort
weight of each possible byte value. The endofstring 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 AZ as for az will
result in a caseinsensitive 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 mostsignificantbyte 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.
Upon successful completion, the value 0 is returned; otherwise the
value 1 is returned and the global variable
errno is set to indicate the error.


 [
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).
sort(1),
qsort(3)
Knuth, D.E.,
Sorting and Searching, The Art of
Computer Programming, Vol. 3,
pp. 170178, 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.
527, 1993.
The
radixsort() function first appeared in
4.4BSD.