projects / unix-history / blame
| 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. |