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