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 | .\" | |
ae59e04c | 6 | .\" @(#)radixsort.3 5.5 (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 | |
18 | .Fn radixsort "u_char **base" "int nmemb" "u_char *table" "u_char endbyte" | |
19 | .Sh DESCRIPTION | |
20 | The | |
21 | .Fn radixsort | |
22 | function | |
f944261e | 23 | is a modified 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. |
f944261e KB |
50 | The end-of-string byte must have a sort weight of 0. |
51 | More than one byte may have the same sort weight. | |
ae59e04c CL |
52 | The |
53 | .Fa table | |
54 | argument | |
f944261e KB |
55 | is useful for applications which wish to sort different characters |
56 | equally; for example, providing a table with the same weights | |
57 | for A-Z as for a-z will result in a case-insensitive sort. | |
ae59e04c CL |
58 | .Pp |
59 | The | |
60 | .Fn radixsort | |
61 | function | |
f944261e KB |
62 | is stable, that is, if two elements compare as equal, their order in |
63 | the sorted array is unchanged. | |
ae59e04c CL |
64 | .Pp |
65 | The | |
66 | .Fn radixsort | |
67 | function | |
79f7b2d7 KB |
68 | is a variant of most-significant-byte radix sorting; in particular, see |
69 | D.E. Knuth's Algorithm R and section 5.2.5, exercise 10. | |
ae59e04c CL |
70 | The |
71 | .Fn radixsort | |
72 | function | |
f944261e | 73 | takes linear time relative to the number of bytes in the strings. |
ae59e04c | 74 | .Sh RETURN VALUES |
f944261e KB |
75 | Upon successful completion 0 is returned. |
76 | Otherwise, \-1 is returned and the global variable | |
ae59e04c | 77 | .Va errno |
f944261e | 78 | is set to indicate the error. |
ae59e04c CL |
79 | .Sh ERRORS |
80 | The | |
81 | .Fn radixsort | |
82 | function | |
f944261e | 83 | may fail and set |
ae59e04c | 84 | .Va errno |
f944261e | 85 | for any of the errors specified for the library routine |
ae59e04c CL |
86 | .Xr malloc 3 . |
87 | .Sh SEE ALSO | |
88 | .Xr sort 1 , | |
89 | .Xr qsort 3 | |
90 | .Pp | |
91 | .Rs | |
92 | .%A Knuth, D.E. | |
93 | .%D 1968 | |
94 | .%B "The Art of Computer Programming" | |
95 | .%T "Sorting and Searching" | |
96 | .%V Vol. 3 | |
97 | .%P pp. 170-178 | |
98 | .Re | |
99 | .Rs | |
100 | .%A Paige, R. | |
101 | .%D 1987 | |
102 | .%T "Three Partition Refinement Algorithms" | |
103 | .%J "SIAM J. Comput." | |
104 | .%V Vol. 16 | |
105 | .%N No. 6 | |
106 | .Re | |
107 | .Sh HISTORY | |
108 | The | |
109 | .Fn radixsort | |
110 | function is | |
111 | .Ud . | |
112 | .Sh BUGS | |
113 | The | |
114 | .Fa nmemb | |
115 | argument | |
116 | must be less than the maximum integer, | |
117 | .Dv INT_MAX . |