1*48350Scael.\" Copyright (c) 1990, 1991 The Regents of the University of California. 245286Sbostic.\" All rights reserved. 345286Sbostic.\" 445286Sbostic.\" %sccs.include.redist.man% 545286Sbostic.\" 6*48350Scael.\" @(#)radixsort.3 5.5 (Berkeley) 04/19/91 745286Sbostic.\" 8*48350Scael.Dd 9*48350Scael.Dt RADIXSORT 3 10*48350Scael.Os 11*48350Scael.Sh NAME 12*48350Scael.Nm radixsort 13*48350Scael.Nd radix sort 14*48350Scael.Sh SYNOPSIS 15*48350Scael.Fd #include <limits.h> 16*48350Scael.Fd #include <stdlib.h> 17*48350Scael.Ft int 18*48350Scael.Fn radixsort "u_char **base" "int nmemb" "u_char *table" "u_char endbyte" 19*48350Scael.Sh DESCRIPTION 20*48350ScaelThe 21*48350Scael.Fn radixsort 22*48350Scaelfunction 2345286Sbosticis a modified radix sort. 24*48350Scael.Pp 2545286SbosticThe 26*48350Scael.Fn radixsort 2745286Sbosticfunction sorts an array of 28*48350Scael.Fa nmemb 2945286Sbosticpointers to byte strings, the initial member of which is referenced 3045286Sbosticby 31*48350Scael.Fa base . 3245286SbosticThe byte strings may contain any values; the end of each string 3345286Sbosticis denoted by the user-specified value 34*48350Scael.Fa endbyte . 3545286SbosticThe contents of the array are sorted in ascending order according 36*48350Scaelto the 37*48350Scael.Tn ASCII 38*48350Scaelorder of the byte strings they reference. 39*48350Scael.Pp 4045286SbosticApplications may specify a sort order by providing the 41*48350Scael.Fa table 4245286Sbosticargument. 43*48350ScaelIf 44*48350Scael.Pf non- Dv NULL , 45*48350Scael.Fa table 46*48350Scaelmust reference an array of 47*48350Scael.Dv UCHAR_MAX 48*48350Scael+ 1 bytes which contains the sort 4945427Sbosticweight of each possible byte value. 5045286SbosticThe end-of-string byte must have a sort weight of 0. 5145286SbosticMore than one byte may have the same sort weight. 52*48350ScaelThe 53*48350Scael.Fa table 54*48350Scaelargument 5545286Sbosticis useful for applications which wish to sort different characters 5645286Sbosticequally; for example, providing a table with the same weights 5745286Sbosticfor A-Z as for a-z will result in a case-insensitive sort. 58*48350Scael.Pp 59*48350ScaelThe 60*48350Scael.Fn radixsort 61*48350Scaelfunction 6245286Sbosticis stable, that is, if two elements compare as equal, their order in 6345286Sbosticthe sorted array is unchanged. 64*48350Scael.Pp 65*48350ScaelThe 66*48350Scael.Fn radixsort 67*48350Scaelfunction 6845565Sbosticis a variant of most-significant-byte radix sorting; in particular, see 6945565SbosticD.E. Knuth's Algorithm R and section 5.2.5, exercise 10. 70*48350ScaelThe 71*48350Scael.Fn radixsort 72*48350Scaelfunction 7345286Sbostictakes linear time relative to the number of bytes in the strings. 74*48350Scael.Sh RETURN VALUES 7545286SbosticUpon successful completion 0 is returned. 7645286SbosticOtherwise, \-1 is returned and the global variable 77*48350Scael.Va errno 7845286Sbosticis set to indicate the error. 79*48350Scael.Sh ERRORS 80*48350ScaelThe 81*48350Scael.Fn radixsort 82*48350Scaelfunction 8345286Sbosticmay fail and set 84*48350Scael.Va errno 8545286Sbosticfor any of the errors specified for the library routine 86*48350Scael.Xr malloc 3 . 87*48350Scael.Sh SEE ALSO 88*48350Scael.Xr sort 1 , 89*48350Scael.Xr qsort 3 90*48350Scael.Pp 91*48350Scael.Rs 92*48350Scael.%A Knuth, D.E. 93*48350Scael.%D 1968 94*48350Scael.%B "The Art of Computer Programming" 95*48350Scael.%T "Sorting and Searching" 96*48350Scael.%V Vol. 3 97*48350Scael.%P pp. 170-178 98*48350Scael.Re 99*48350Scael.Rs 100*48350Scael.%A Paige, R. 101*48350Scael.%D 1987 102*48350Scael.%T "Three Partition Refinement Algorithms" 103*48350Scael.%J "SIAM J. Comput." 104*48350Scael.%V Vol. 16 105*48350Scael.%N No. 6 106*48350Scael.Re 107*48350Scael.Sh HISTORY 108*48350ScaelThe 109*48350Scael.Fn radixsort 110*48350Scaelfunction is 111*48350Scael.Ud . 112*48350Scael.Sh BUGS 113*48350ScaelThe 114*48350Scael.Fa nmemb 115*48350Scaelargument 116*48350Scaelmust be less than the maximum integer, 117*48350Scael.Dv INT_MAX . 118