Commit | Line | Data |
---|---|---|
ae59e04c | 1 | .\" Copyright (c) 1990, 1991 The Regents of the University of California. |
f944261e KB |
2 | .\" All rights reserved. |
3 | .\" | |
4 | .\" %sccs.include.redist.man% | |
5 | .\" | |
a0451f54 | 6 | .\" @(#)radixsort.3 5.8 (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" |
ae59e04c CL |
19 | .Sh DESCRIPTION |
20 | The | |
21 | .Fn radixsort | |
22 | function | |
a0451f54 | 23 | is a radix sort. |
ae59e04c | 24 | .Pp |
f944261e | 25 | The |
ae59e04c | 26 | .Fn radixsort |
f944261e | 27 | function sorts an array of |
ae59e04c | 28 | .Fa nmemb |
f944261e KB |
29 | pointers to byte strings, the initial member of which is referenced |
30 | 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 . |
f944261e | 35 | The contents of the array are sorted in ascending order according |
ae59e04c CL |
36 | to the |
37 | .Tn ASCII | |
38 | order of the byte strings they reference. | |
39 | .Pp | |
f944261e | 40 | Applications may specify a sort order by providing the |
ae59e04c | 41 | .Fa table |
f944261e | 42 | argument. |
ae59e04c CL |
43 | If |
44 | .Pf non- Dv NULL , | |
45 | .Fa table | |
46 | must reference an array of | |
47 | .Dv UCHAR_MAX | |
48 | + 1 bytes which contains the sort | |
e061e641 | 49 | weight of each possible byte value. |
a0451f54 KB |
50 | The end-of-string byte must have a sort weight of 0 or 255 |
51 | (for sorting in reverse order). | |
f944261e | 52 | More than one byte may have the same sort weight. |
ae59e04c CL |
53 | The |
54 | .Fa table | |
55 | argument | |
f944261e KB |
56 | is useful for applications which wish to sort different characters |
57 | equally; for example, providing a table with the same weights | |
58 | for A-Z as for a-z will result in a case-insensitive sort. | |
a0451f54 KB |
59 | If |
60 | .Fa table | |
61 | is NULL, | |
62 | ASCII weights are used and | |
63 | .Fa endbyte | |
64 | has a sorting weight of 0. | |
ae59e04c CL |
65 | .Pp |
66 | The | |
67 | .Fn radixsort | |
68 | function | |
f944261e KB |
69 | is stable, that is, if two elements compare as equal, their order in |
70 | the sorted array is unchanged. | |
ae59e04c CL |
71 | .Pp |
72 | The | |
73 | .Fn radixsort | |
74 | function | |
79f7b2d7 KB |
75 | is a variant of most-significant-byte radix sorting; in particular, see |
76 | D.E. Knuth's Algorithm R and section 5.2.5, exercise 10. | |
ae59e04c CL |
77 | The |
78 | .Fn radixsort | |
79 | function | |
f944261e | 80 | takes 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 | |
ae59e04c CL |
97 | .Fn radixsort |
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 | |
123 | .Sh HISTORY | |
124 | The | |
125 | .Fn radixsort | |
126 | function is | |
127 | .Ud . |