lib/libc/stdlib/radixsort.3

   1 .\" Copyright (c) 1990, 1991, 1993
   2 .\"     The Regents of the University of California.  All rights reserved.
   3 .\"
   4 .\" Redistribution and use in source and binary forms, with or without
   5 .\" modification, are permitted provided that the following conditions
   6 .\" are met:
   7 .\" 1. Redistributions of source code must retain the above copyright
   8 .\"    notice, this list of conditions and the following disclaimer.
   9 .\" 2. Redistributions in binary form must reproduce the above copyright
  10 .\"    notice, this list of conditions and the following disclaimer in the
  11 .\"    documentation and/or other materials provided with the distribution.
  12 .\" 3. Neither the name of the University nor the names of its contributors
  13 .\"    may be used to endorse or promote products derived from this software
  14 .\"    without specific prior written permission.
  15 .\"
  16 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  17 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  20 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  21 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  22 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  23 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  24 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  25 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  26 .\" SUCH DAMAGE.
  27 .\"
  28 .Dd January 27, 1994
  29 .Dt RADIXSORT 3
  30 .Os
  31 .Sh NAME
  32 .Nm radixsort , sradixsort
  33 .Nd radix sort
  34 .Sh LIBRARY
  35 .Lb libc
  36 .Sh SYNOPSIS
  37 .In limits.h
  38 .In stdlib.h
  39 .Ft int
  40 .Fn radixsort "const unsigned char **base" "int nmemb" "const unsigned char *table" "unsigned endbyte"
  41 .Ft int
  42 .Fn sradixsort "const unsigned char **base" "int nmemb" "const unsigned char *table" "unsigned endbyte"
  43 .Sh DESCRIPTION
  44 The
  45 .Fn radixsort
  46 and
  47 .Fn sradixsort
  48 functions
  49 are implementations of radix sort.
  50 .Pp
  51 These functions sort an array of pointers to byte strings, the initial
  52 member of which is referenced by
  53 .Fa base .
  54 The byte strings may contain any values; the end of each string
  55 is denoted by the user-specified value
  56 .Fa endbyte .
  57 .Pp
  58 Applications may specify a sort order by providing the
  59 .Fa table
  60 argument.
  61 If
  62 .Pf non- Dv NULL ,
  63 .Fa table
  64 must reference an array of
  65 .Dv UCHAR_MAX
  66 + 1 bytes which contains the sort
  67 weight of each possible byte value.
  68 The end-of-string byte must have a sort weight of 0 or 255
  69 (for sorting in reverse order).
  70 More than one byte may have the same sort weight.
  71 The
  72 .Fa table
  73 argument
  74 is useful for applications which wish to sort different characters
  75 equally, for example, providing a table with the same weights
  76 for A-Z as for a-z will result in a case-insensitive sort.
  77 If
  78 .Fa table
  79 is NULL, the contents of the array are sorted in ascending order
  80 according to the
  81 .Tn ASCII
  82 order of the byte strings they reference and
  83 .Fa endbyte
  84 has a sorting weight of 0.
  85 .Pp
  86 The
  87 .Fn sradixsort
  88 function is stable, that is, if two elements compare as equal, their
  89 order in the sorted array is unchanged.
  90 The
  91 .Fn sradixsort
  92 function uses additional memory sufficient to hold
  93 .Fa nmemb
  94 pointers.
  95 .Pp
  96 The
  97 .Fn radixsort
  98 function is not stable, but uses no additional memory.
  99 .Pp
 100 These functions are variants of most-significant-byte radix sorting; in
 101 particular, see
 102 .An "D.E. Knuth" Ns 's
 103 .%T "Algorithm R"
 104 and section 5.2.5, exercise 10.
 105 They take linear time relative to the number of bytes in the strings.
 106 .Sh RETURN VALUES
 107 .Rv -std radixsort
 108 .Sh ERRORS
 109 .Bl -tag -width Er
 110 .It Bq Er EINVAL
 111 The value of the
 112 .Fa endbyte
 113 element of
 114 .Fa table
 115 is not 0 or 255.
 116 .El
 117 .Pp
 118 Additionally, the
 119 .Fn sradixsort
 120 function
 121 may fail and set
 122 .Va errno
 123 for any of the errors specified for the library routine
 124 .Xr malloc 3 .
 125 .Sh SEE ALSO
 126 .Xr sort 1 ,
 127 .Xr qsort 3
 128 .Pp
 129 .Rs
 130 .%A Knuth, D.E.
 131 .%D 1968
 132 .%B "The Art of Computer Programming"
 133 .%T "Sorting and Searching"
 134 .%V Vol. 3
 135 .%P pp. 170-178
 136 .Re
 137 .Rs
 138 .%A Paige, R.
 139 .%D 1987
 140 .%T "Three Partition Refinement Algorithms"
 141 .%J "SIAM J. Comput."
 142 .%V Vol. 16
 143 .%N No. 6
 144 .Re
 145 .Rs
 146 .%A McIlroy, P.
 147 .%D 1993
 148 .%B "Engineering Radix Sort"
 149 .%T "Computing Systems"
 150 .%V Vol. 6:1
 151 .%P pp. 5-27
 152 .Re
 153 .Sh HISTORY
 154 The
 155 .Fn radixsort
 156 function first appeared in
 157 .Bx 4.4 .