Commit | Line | Data |
---|---|---|
f9922951 KB |
1 | .\" Copyright (c) 1990, 1991, 1993 |
2 | .\" The Regents of the University of California. All rights reserved. | |
f944261e KB |
3 | .\" |
4 | .\" %sccs.include.redist.man% | |
5 | .\" | |
dad8117b | 6 | .\" @(#)radixsort.3 8.2 (Berkeley) %G% |
f944261e | 7 | .\" |
ae59e04c CL |
8 | .Dd |
9 | .Dt RADIXSORT 3 | |
10 | .Os | |
11 | .Sh NAME | |
12 | .Nm radixsort | |
13 | .Nd radix sort | |
14 | .Sh SYNOPSIS | |
15 | .Fd #include <limits.h> | |
16 | .Fd #include <stdlib.h> | |
17 | .Ft int | |
65c76a10 | 18 | .Fn radixsort "u_char **base" "int nmemb" "u_char *table" "u_int endbyte" |
6f4f6081 KB |
19 | .Ft int |
20 | .Fn sradixsort "u_char **base" "int nmemb" "u_char *table" "u_int endbyte" | |
ae59e04c CL |
21 | .Sh DESCRIPTION |
22 | The | |
23 | .Fn radixsort | |
6f4f6081 KB |
24 | and |
25 | .Fn sradixsort | |
26 | functions | |
27 | are implementations of radix sort. | |
ae59e04c | 28 | .Pp |
6f4f6081 KB |
29 | These functions sort an array of pointers to byte strings, the initial |
30 | member of which is referenced by | |
ae59e04c | 31 | .Fa base . |
f944261e KB |
32 | The byte strings may contain any values; the end of each string |
33 | is denoted by the user-specified value | |
ae59e04c | 34 | .Fa endbyte . |
ae59e04c | 35 | .Pp |
f944261e | 36 | Applications may specify a sort order by providing the |
ae59e04c | 37 | .Fa table |
f944261e | 38 | argument. |
ae59e04c CL |
39 | If |
40 | .Pf non- Dv NULL , | |
41 | .Fa table | |
42 | must reference an array of | |
43 | .Dv UCHAR_MAX | |
44 | + 1 bytes which contains the sort | |
e061e641 | 45 | weight of each possible byte value. |
a0451f54 KB |
46 | The end-of-string byte must have a sort weight of 0 or 255 |
47 | (for sorting in reverse order). | |
f944261e | 48 | More than one byte may have the same sort weight. |
ae59e04c CL |
49 | The |
50 | .Fa table | |
51 | argument | |
f944261e | 52 | is useful for applications which wish to sort different characters |
6f4f6081 | 53 | equally, for example, providing a table with the same weights |
f944261e | 54 | for A-Z as for a-z will result in a case-insensitive sort. |
a0451f54 KB |
55 | If |
56 | .Fa table | |
6f4f6081 KB |
57 | is NULL, the contents of the array are sorted in ascending order |
58 | according to the | |
59 | .Tn ASCII | |
60 | order of the byte strings they reference and | |
a0451f54 KB |
61 | .Fa endbyte |
62 | has a sorting weight of 0. | |
ae59e04c CL |
63 | .Pp |
64 | The | |
6f4f6081 KB |
65 | .Fn sradixsort |
66 | function is stable, that is, if two elements compare as equal, their | |
67 | order in the sorted array is unchanged. | |
ae59e04c | 68 | The |
6f4f6081 KB |
69 | .Fn sradixsort |
70 | function uses additional memory sufficient to hold | |
71 | .Fa nmemb | |
72 | pointers. | |
73 | .Pp | |
ae59e04c CL |
74 | The |
75 | .Fn radixsort | |
6f4f6081 KB |
76 | function is not stable, but uses no additional memory. |
77 | .Pp | |
78 | These functions are variants of most-significant-byte radix sorting; in | |
79 | particular, see D.E. Knuth's Algorithm R and section 5.2.5, exercise 10. | |
80 | They take linear time relative to the number of bytes in the strings. | |
ae59e04c | 81 | .Sh RETURN VALUES |
f944261e KB |
82 | Upon successful completion 0 is returned. |
83 | Otherwise, \-1 is returned and the global variable | |
ae59e04c | 84 | .Va errno |
f944261e | 85 | is set to indicate the error. |
ae59e04c | 86 | .Sh ERRORS |
a0451f54 KB |
87 | .Bl -tag -width Er |
88 | .It Bq Er EINVAL | |
89 | The value of the | |
90 | .Fa endbyte | |
91 | element of | |
92 | .Fa table | |
93 | is not 0 or 255. | |
94 | .El | |
95 | .Pp | |
96 | Additionally, the | |
6f4f6081 | 97 | .Fn sradixsort |
ae59e04c | 98 | function |
f944261e | 99 | may fail and set |
ae59e04c | 100 | .Va errno |
f944261e | 101 | for any of the errors specified for the library routine |
ae59e04c CL |
102 | .Xr malloc 3 . |
103 | .Sh SEE ALSO | |
104 | .Xr sort 1 , | |
105 | .Xr qsort 3 | |
106 | .Pp | |
107 | .Rs | |
108 | .%A Knuth, D.E. | |
109 | .%D 1968 | |
110 | .%B "The Art of Computer Programming" | |
111 | .%T "Sorting and Searching" | |
112 | .%V Vol. 3 | |
113 | .%P pp. 170-178 | |
114 | .Re | |
115 | .Rs | |
116 | .%A Paige, R. | |
117 | .%D 1987 | |
118 | .%T "Three Partition Refinement Algorithms" | |
119 | .%J "SIAM J. Comput." | |
120 | .%V Vol. 16 | |
121 | .%N No. 6 | |
122 | .Re | |
dad8117b KB |
123 | .Rs |
124 | .%A McIlroy, P. | |
125 | .%D 1993 | |
126 | .%B "Engineering Radix Sort" | |
127 | .%T "Computing Systems" | |
128 | .%V Vol. 6:1 | |
129 | .%P pp. 5-27 | |
130 | .Re | |
ae59e04c CL |
131 | .Sh HISTORY |
132 | The | |
133 | .Fn radixsort | |
bf67d36e | 134 | function first appeared in 4.4BSD. |