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 .\" $DragonFly: src/lib/libcr/stdlib/Attic/radixsort.3,v 1.2 2003/06/17 04:26:46 dillon Exp $
  35 .\"
  36 .Dd January 27, 1994
  37 .Dt RADIXSORT 3
  38 .Os
  39 .Sh NAME
  40 .Nm radixsort
  41 .Nd radix sort
  42 .Sh LIBRARY
  43 .Lb libc
  44 .Sh SYNOPSIS
  45 .In limits.h
  46 .In stdlib.h
  47 .Ft int
  48 .Fn radixsort "const unsigned char **base" "int nmemb" "const unsigned char *table" "unsigned endbyte"
  49 .Ft int
  50 .Fn sradixsort "const unsigned char **base" "int nmemb" "const unsigned char *table" "unsigned endbyte"
  51 .Sh DESCRIPTION
  52 The
  53 .Fn radixsort
  54 and
  55 .Fn sradixsort
  56 functions
  57 are implementations of radix sort.
  58 .Pp
  59 These functions sort an array of pointers to byte strings, the initial
  60 member of which is referenced by
  61 .Fa base .
  62 The byte strings may contain any values; the end of each string
  63 is denoted by the user-specified value
  64 .Fa endbyte .
  65 .Pp
  66 Applications may specify a sort order by providing the
  67 .Fa table
  68 argument.
  69 If
  70 .Pf non- Dv NULL ,
  71 .Fa table
  72 must reference an array of
  73 .Dv UCHAR_MAX
  74 + 1 bytes which contains the sort
  75 weight of each possible byte value.
  76 The end-of-string byte must have a sort weight of 0 or 255
  77 (for sorting in reverse order).
  78 More than one byte may have the same sort weight.
  79 The
  80 .Fa table
  81 argument
  82 is useful for applications which wish to sort different characters
  83 equally, for example, providing a table with the same weights
  84 for A-Z as for a-z will result in a case-insensitive sort.
  85 If
  86 .Fa table
  87 is NULL, the contents of the array are sorted in ascending order
  88 according to the
  89 .Tn ASCII
  90 order of the byte strings they reference and
  91 .Fa endbyte
  92 has a sorting weight of 0.
  93 .Pp
  94 The
  95 .Fn sradixsort
  96 function is stable, that is, if two elements compare as equal, their
  97 order in the sorted array is unchanged.
  98 The
  99 .Fn sradixsort
 100 function uses additional memory sufficient to hold
 101 .Fa nmemb
 102 pointers.
 103 .Pp
 104 The
 105 .Fn radixsort
 106 function is not stable, but uses no additional memory.
 107 .Pp
 108 These functions are variants of most-significant-byte radix sorting; in
 109 particular, see D.E. Knuth's Algorithm R and section 5.2.5, exercise 10.
 110 They take linear time relative to the number of bytes in the strings.
 111 .Sh RETURN VALUES
 112 .Rv -std radixsort
 113 .Sh ERRORS
 114 .Bl -tag -width Er
 115 .It Bq Er EINVAL
 116 The value of the
 117 .Fa endbyte
 118 element of
 119 .Fa table
 120 is not 0 or 255.
 121 .El
 122 .Pp
 123 Additionally, the
 124 .Fn sradixsort
 125 function
 126 may fail and set
 127 .Va errno
 128 for any of the errors specified for the library routine
 129 .Xr malloc 3 .
 130 .Sh SEE ALSO
 131 .Xr sort 1 ,
 132 .Xr qsort 3
 133 .Pp
 134 .Rs
 135 .%A Knuth, D.E.
 136 .%D 1968
 137 .%B "The Art of Computer Programming"
 138 .%T "Sorting and Searching"
 139 .%V Vol. 3
 140 .%P pp. 170-178
 141 .Re
 142 .Rs
 143 .%A Paige, R.
 144 .%D 1987
 145 .%T "Three Partition Refinement Algorithms"
 146 .%J "SIAM J. Comput."
 147 .%V Vol. 16
 148 .%N No. 6
 149 .Re
 150 .Rs
 151 .%A McIlroy, P.
 152 .%D 1993
 153 .%B "Engineering Radix Sort"
 154 .%T "Computing Systems"
 155 .%V Vol. 6:1
 156 .%P pp. 5-27
 157 .Re
 158 .Sh HISTORY
 159 The
 160 .Fn radixsort
 161 function first appeared in
 162 .Bx 4.4 .