*nix Documentation Project
·  Home
 +   man pages
·  Linux HOWTOs
·  FreeBSD Tips
·  *niX Forums

  man pages->OpenBSD man pages -> radixsort (3)              



NAME    [Toc]    [Back]

     radixsort, sradixsort - radix sort

SYNOPSIS    [Toc]    [Back]

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

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

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

DESCRIPTION    [Toc]    [Back]

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

     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

     Applications may specify a sort order by providing the table
     If  non-null, table must reference an array of UCHAR_MAX + 1
bytes which
     contains the sort weight of each possible byte  value.   The
     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
     function uses additional memory  sufficient  to  hold  nmemb

     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

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
     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
[ Back ]
 Similar pages
Name OS Title
l64a OpenBSD convert between 32-bit integer and radix-64 ASCII string
a64l OpenBSD convert between 32-bit integer and radix-64 ASCII string
tsort IRIX topological sort
heapsort OpenBSD sort functions
mergesort OpenBSD sort functions
qsort IRIX quick sort
qsort OpenBSD sort functions
qsort IRIX quicker sort
tsort HP-UX topological sort
mergesort NetBSD sort functions
Copyright © 2004-2005 DeniX Solutions SRL
newsletter delivery service