[apple/libc.git] / stdlib / radixsort.3

.\" Copyright (c) 1990, 1991, 1993
.\"	The Regents of the University of California.  All rights reserved.
.\"
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" are met:
.\" 1. Redistributions of source code must retain the above copyright
.\"    notice, this list of conditions and the following disclaimer.
.\" 2. Redistributions in binary form must reproduce the above copyright
.\"    notice, this list of conditions and the following disclaimer in the
.\"    documentation and/or other materials provided with the distribution.
.\" 3. All advertising materials mentioning features or use of this software
.\"    must display the following acknowledgement:
.\"	This product includes software developed by the University of
.\"	California, Berkeley and its contributors.
.\" 4. Neither the name of the University nor the names of its contributors
.\"    may be used to endorse or promote products derived from this software
.\"    without specific prior written permission.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
.\" SUCH DAMAGE.
.\"
.\"     @(#)radixsort.3	8.2 (Berkeley) 1/27/94
.\" $FreeBSD: src/lib/libc/stdlib/radixsort.3,v 1.9 2001/09/07 14:46:35 asmodai Exp $
.\"
.Dd January 27, 1994
.Dt RADIXSORT 3
.Os
.Sh NAME
.Nm radixsort
.Nd radix sort
.Sh LIBRARY
.Lb libc
.Sh SYNOPSIS
.In limits.h
.In stdlib.h
.Ft int
.Fn radixsort "const unsigned char **base" "int nmemb" "const unsigned char *table" "unsigned endbyte"
.Ft int
.Fn sradixsort "const unsigned char **base" "int nmemb" "const unsigned char *table" "unsigned endbyte"
.Sh DESCRIPTION
The
.Fn radixsort
and
.Fn sradixsort
functions
are implementations of radix sort.
.Pp
These functions sort an array of pointers to byte strings, the initial
member of which is referenced by
.Fa base .
The byte strings may contain any values; the end of each string
is denoted by the user-specified value
.Fa endbyte .
.Pp
Applications may specify a sort order by providing the
.Fa table
argument.
If
.Pf non- Dv NULL ,
.Fa table
must reference an array of
.Dv UCHAR_MAX
+ 1 bytes which contains the sort
weight of each possible byte value.
The end-of-string 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
.Fa 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
.Fa table
is NULL, the contents of the array are sorted in ascending order
according to the
.Tn ASCII
order of the byte strings they reference and
.Fa endbyte
has a sorting weight of 0.
.Pp
The
.Fn sradixsort
function is stable, that is, if two elements compare as equal, their
order in the sorted array is unchanged.
The
.Fn sradixsort
function uses additional memory sufficient to hold
.Fa nmemb
pointers.
.Pp
The
.Fn radixsort
function is not stable, but uses no additional memory.
.Pp
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 strings.
.Sh RETURN VALUES
.Rv -std radixsort
.Sh ERRORS
.Bl -tag -width Er
.It Bq Er EINVAL
The value of the
.Fa endbyte
element of
.Fa table
is not 0 or 255.
.El
.Pp
Additionally, the
.Fn sradixsort
function
may fail and set
.Va errno
for any of the errors specified for the library routine
.Xr malloc 3 .
.Sh SEE ALSO
.Xr sort 1 ,
.Xr qsort 3
.Pp
.Rs
.%A Knuth, D.E.
.%D 1968
.%B "The Art of Computer Programming"
.%T "Sorting and Searching"
.%V Vol. 3
.%P pp. 170-178
.Re
.Rs
.%A Paige, R.
.%D 1987
.%T "Three Partition Refinement Algorithms"
.%J "SIAM J. Comput."
.%V Vol. 16
.%N No. 6
.Re
.Rs
.%A McIlroy, P.
.%D 1993
.%B "Engineering Radix Sort"
.%T "Computing Systems"
.%V Vol. 6:1
.%P pp. 5-27
.Re
.Sh HISTORY
The
.Fn radixsort
function first appeared in
.Bx 4.4 .
Commit	Line	Data
5b2abdfb A	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.9 2001/09/07 14:46:35 asmodai 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 .