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