1.\" Copyright (c) 1990, 1991 The Regents of the University of California. 2.\" 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.\" from: @(#)radixsort.3 5.5 (Berkeley) 4/19/91 33.\" $Id: radixsort.3,v 1.2 1993/08/01 07:44:21 mycroft Exp $ 34.\" 35.Dd April 19, 1991 36.Dt RADIXSORT 3 37.Os 38.Sh NAME 39.Nm radixsort 40.Nd radix sort 41.Sh SYNOPSIS 42.Fd #include <limits.h> 43.Fd #include <stdlib.h> 44.Ft int 45.Fn radixsort "u_char **base" "int nmemb" "u_char *table" "u_char endbyte" 46.Sh DESCRIPTION 47The 48.Fn radixsort 49function 50is a modified radix sort. 51.Pp 52The 53.Fn radixsort 54function sorts an array of 55.Fa nmemb 56pointers to byte strings, the initial member of which is referenced 57by 58.Fa base . 59The byte strings may contain any values; the end of each string 60is denoted by the user-specified value 61.Fa endbyte . 62The contents of the array are sorted in ascending order according 63to the 64.Tn ASCII 65order of the byte strings they reference. 66.Pp 67Applications may specify a sort order by providing the 68.Fa table 69argument. 70If 71.Pf non- Dv NULL , 72.Fa table 73must reference an array of 74.Dv UCHAR_MAX 75+ 1 bytes which contains the sort 76weight of each possible byte value. 77The end-of-string byte must have a sort weight of 0. 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. 85.Pp 86The 87.Fn radixsort 88function 89is stable, that is, if two elements compare as equal, their order in 90the sorted array is unchanged. 91.Pp 92The 93.Fn radixsort 94function 95is a variant of most-significant-byte radix sorting; in particular, see 96D.E. Knuth's Algorithm R and section 5.2.5, exercise 10. 97The 98.Fn radixsort 99function 100takes linear time relative to the number of bytes in the strings. 101.Sh RETURN VALUES 102Upon successful completion 0 is returned. 103Otherwise, \-1 is returned and the global variable 104.Va errno 105is set to indicate the error. 106.Sh ERRORS 107The 108.Fn radixsort 109function 110may fail and set 111.Va errno 112for any of the errors specified for the library routine 113.Xr malloc 3 . 114.Sh SEE ALSO 115.Xr sort 1 , 116.Xr qsort 3 117.Pp 118.Rs 119.%A Knuth, D.E. 120.%D 1968 121.%B "The Art of Computer Programming" 122.%T "Sorting and Searching" 123.%V Vol. 3 124.%P pp. 170-178 125.Re 126.Rs 127.%A Paige, R. 128.%D 1987 129.%T "Three Partition Refinement Algorithms" 130.%J "SIAM J. Comput." 131.%V Vol. 16 132.%N No. 6 133.Re 134.Sh HISTORY 135The 136.Fn radixsort 137function is 138.Ud . 139.Sh BUGS 140The 141.Fa nmemb 142argument 143must be less than the maximum integer, 144.Dv INT_MAX . 145