148350Scael.\" Copyright (c) 1990, 1991 The Regents of the University of California. 245286Sbostic.\" All rights reserved. 345286Sbostic.\" 445286Sbostic.\" %sccs.include.redist.man% 545286Sbostic.\" 6*50481Sbostic.\" @(#)radixsort.3 5.6 (Berkeley) 07/23/91 745286Sbostic.\" 848350Scael.Dd 948350Scael.Dt RADIXSORT 3 1048350Scael.Os 1148350Scael.Sh NAME 1248350Scael.Nm radixsort 1348350Scael.Nd radix sort 1448350Scael.Sh SYNOPSIS 1548350Scael.Fd #include <limits.h> 1648350Scael.Fd #include <stdlib.h> 1748350Scael.Ft int 18*50481Sbostic.Fn radixsort "u_char **base" "int nmemb" "u_char *table" "u_int endbyte" 1948350Scael.Sh DESCRIPTION 2048350ScaelThe 2148350Scael.Fn radixsort 2248350Scaelfunction 2345286Sbosticis a modified radix sort. 2448350Scael.Pp 2545286SbosticThe 2648350Scael.Fn radixsort 2745286Sbosticfunction sorts an array of 2848350Scael.Fa nmemb 2945286Sbosticpointers to byte strings, the initial member of which is referenced 3045286Sbosticby 3148350Scael.Fa base . 3245286SbosticThe byte strings may contain any values; the end of each string 3345286Sbosticis denoted by the user-specified value 3448350Scael.Fa endbyte . 3545286SbosticThe contents of the array are sorted in ascending order according 3648350Scaelto the 3748350Scael.Tn ASCII 3848350Scaelorder of the byte strings they reference. 3948350Scael.Pp 4045286SbosticApplications may specify a sort order by providing the 4148350Scael.Fa table 4245286Sbosticargument. 4348350ScaelIf 4448350Scael.Pf non- Dv NULL , 4548350Scael.Fa table 4648350Scaelmust reference an array of 4748350Scael.Dv UCHAR_MAX 4848350Scael+ 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. 5248350ScaelThe 5348350Scael.Fa table 5448350Scaelargument 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. 5848350Scael.Pp 5948350ScaelThe 6048350Scael.Fn radixsort 6148350Scaelfunction 6245286Sbosticis stable, that is, if two elements compare as equal, their order in 6345286Sbosticthe sorted array is unchanged. 6448350Scael.Pp 6548350ScaelThe 6648350Scael.Fn radixsort 6748350Scaelfunction 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. 7048350ScaelThe 7148350Scael.Fn radixsort 7248350Scaelfunction 7345286Sbostictakes linear time relative to the number of bytes in the strings. 7448350Scael.Sh RETURN VALUES 7545286SbosticUpon successful completion 0 is returned. 7645286SbosticOtherwise, \-1 is returned and the global variable 7748350Scael.Va errno 7845286Sbosticis set to indicate the error. 7948350Scael.Sh ERRORS 8048350ScaelThe 8148350Scael.Fn radixsort 8248350Scaelfunction 8345286Sbosticmay fail and set 8448350Scael.Va errno 8545286Sbosticfor any of the errors specified for the library routine 8648350Scael.Xr malloc 3 . 8748350Scael.Sh SEE ALSO 8848350Scael.Xr sort 1 , 8948350Scael.Xr qsort 3 9048350Scael.Pp 9148350Scael.Rs 9248350Scael.%A Knuth, D.E. 9348350Scael.%D 1968 9448350Scael.%B "The Art of Computer Programming" 9548350Scael.%T "Sorting and Searching" 9648350Scael.%V Vol. 3 9748350Scael.%P pp. 170-178 9848350Scael.Re 9948350Scael.Rs 10048350Scael.%A Paige, R. 10148350Scael.%D 1987 10248350Scael.%T "Three Partition Refinement Algorithms" 10348350Scael.%J "SIAM J. Comput." 10448350Scael.%V Vol. 16 10548350Scael.%N No. 6 10648350Scael.Re 10748350Scael.Sh HISTORY 10848350ScaelThe 10948350Scael.Fn radixsort 11048350Scaelfunction is 11148350Scael.Ud . 11248350Scael.Sh BUGS 11348350ScaelThe 11448350Scael.Fa nmemb 11548350Scaelargument 11648350Scaelmust be less than the maximum integer, 11748350Scael.Dv INT_MAX . 118