diff options
Diffstat (limited to 'lib/libc/stdlib/radixsort.3')
| -rw-r--r-- | lib/libc/stdlib/radixsort.3 | 143 |
1 files changed, 143 insertions, 0 deletions
diff --git a/lib/libc/stdlib/radixsort.3 b/lib/libc/stdlib/radixsort.3 new file mode 100644 index 000000000000..0575ec798c63 --- /dev/null +++ b/lib/libc/stdlib/radixsort.3 @@ -0,0 +1,143 @@ +.\" Copyright (c) 1990, 1991 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 5.5 (Berkeley) 4/19/91 +.\" +.Dd April 19, 1991 +.Dt RADIXSORT 3 +.Os +.Sh NAME +.Nm radixsort +.Nd radix sort +.Sh SYNOPSIS +.Fd #include <limits.h> +.Fd #include <stdlib.h> +.Ft int +.Fn radixsort "u_char **base" "int nmemb" "u_char *table" "u_char endbyte" +.Sh DESCRIPTION +The +.Fn radixsort +function +is a modified radix sort. +.Pp +The +.Fn radixsort +function sorts an array of +.Fa nmemb +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 . +The contents of the array are sorted in ascending order according +to the +.Tn ASCII +order of the byte strings they reference. +.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. +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. +.Pp +The +.Fn radixsort +function +is stable, that is, if two elements compare as equal, their order in +the sorted array is unchanged. +.Pp +The +.Fn radixsort +function +is a variant of most-significant-byte radix sorting; in particular, see +D.E. Knuth's Algorithm R and section 5.2.5, exercise 10. +The +.Fn radixsort +function +takes linear time relative to the number of bytes in the strings. +.Sh RETURN VALUES +Upon successful completion 0 is returned. +Otherwise, \-1 is returned and the global variable +.Va errno +is set to indicate the error. +.Sh ERRORS +The +.Fn radixsort +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 +.Sh HISTORY +The +.Fn radixsort +function is +.Ud . +.Sh BUGS +The +.Fa nmemb +argument +must be less than the maximum integer, +.Dv INT_MAX . |