Commit | Line | Data |
---|---|---|
f944261e KB |
1 | .\" Copyright (c) 1990 The Regents of the University of California. |
2 | .\" All rights reserved. | |
3 | .\" | |
4 | .\" %sccs.include.redist.man% | |
5 | .\" | |
70c0cb05 | 6 | .\" @(#)radixsort.3 5.4 (Berkeley) %G% |
f944261e KB |
7 | .\" |
8 | .TH radixsort 3 "" | |
9 | .SH NAME | |
10 | radixsort \- radix sort | |
11 | .SH SYNOPSIS | |
12 | .nf | |
13 | .ft B | |
14 | #include <limits.h> | |
15 | #include <stdlib.h> | |
16 | ||
17 | radixsort(u_char **base, int nmemb, u_char *table, u_char endbyte); | |
18 | .ft R | |
19 | .fi | |
20 | .SH DESCRIPTION | |
21 | .I Radixsort | |
22 | is a modified radix sort. | |
23 | .PP | |
24 | The | |
25 | .I radixsort | |
26 | function sorts an array of | |
27 | .I nmemb | |
28 | pointers to byte strings, the initial member of which is referenced | |
29 | by | |
30 | .IR base . | |
31 | The byte strings may contain any values; the end of each string | |
32 | is denoted by the user-specified value | |
33 | .IR endbyte . | |
34 | The contents of the array are sorted in ascending order according | |
35 | to the ASCII order of the byte strings they reference. | |
36 | .PP | |
37 | Applications may specify a sort order by providing the | |
38 | .IR table | |
39 | argument. | |
40 | If non-NULL, | |
41 | .I table | |
e061e641 KB |
42 | must reference an array of UCHAR_MAX + 1 bytes which contains the sort |
43 | weight of each possible byte value. | |
f944261e KB |
44 | The end-of-string byte must have a sort weight of 0. |
45 | More than one byte may have the same sort weight. | |
46 | .I Table | |
47 | is useful for applications which wish to sort different characters | |
48 | equally; for example, providing a table with the same weights | |
49 | for A-Z as for a-z will result in a case-insensitive sort. | |
50 | .PP | |
51 | .I Radixsort | |
52 | is stable, that is, if two elements compare as equal, their order in | |
53 | the sorted array is unchanged. | |
54 | .PP | |
55 | .I Radixsort | |
79f7b2d7 KB |
56 | is a variant of most-significant-byte radix sorting; in particular, see |
57 | D.E. Knuth's Algorithm R and section 5.2.5, exercise 10. | |
f944261e KB |
58 | .I Radixsort |
59 | takes linear time relative to the number of bytes in the strings. | |
60 | .SH SEE ALSO | |
61 | sort(1), qsort(3) | |
79f7b2d7 KB |
62 | .sp |
63 | Knuth, D.E. [1968]. "The Art of Computer Programming Vol. 3: | |
64 | Sorting and Searching", pp. 170-178. | |
65 | .br | |
66 | Paige, R. [1987]. "Three Partition Refinement Algorithms", | |
67 | SIAM J. Comput. Vol. 16, No. 6. | |
f944261e KB |
68 | .SH "RETURN VALUES" |
69 | Upon successful completion 0 is returned. | |
70 | Otherwise, \-1 is returned and the global variable | |
71 | .I errno | |
72 | is set to indicate the error. | |
73 | .SH ERRORS | |
74 | .I Radixsort | |
75 | may fail and set | |
76 | .I errno | |
77 | for any of the errors specified for the library routine | |
78 | .IR malloc (3). | |
70c0cb05 KB |
79 | .SH BUGS |
80 | .I Nmemb | |
81 | must be less than the maximum integer, INT_MAX. |