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