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