148350Scael.\" Copyright (c) 1990, 1991 The Regents of the University of California. 245286Sbostic.\" All rights reserved. 345286Sbostic.\" 445286Sbostic.\" %sccs.include.redist.man% 545286Sbostic.\" 6*51687Sbostic.\" @(#)radixsort.3 5.8 (Berkeley) 11/13/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 1850481Sbostic.Fn radixsort "u_char **base" "int nmemb" "u_char *table" "u_int endbyte" 1948350Scael.Sh DESCRIPTION 2048350ScaelThe 2148350Scael.Fn radixsort 2248350Scaelfunction 23*51687Sbosticis a 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. 50*51687SbosticThe end-of-string byte must have a sort weight of 0 or 255 51*51687Sbostic(for sorting in reverse order). 5245286SbosticMore than one byte may have the same sort weight. 5348350ScaelThe 5448350Scael.Fa table 5548350Scaelargument 5645286Sbosticis useful for applications which wish to sort different characters 5745286Sbosticequally; for example, providing a table with the same weights 5845286Sbosticfor A-Z as for a-z will result in a case-insensitive sort. 59*51687SbosticIf 60*51687Sbostic.Fa table 61*51687Sbosticis NULL, 62*51687SbosticASCII weights are used and 63*51687Sbostic.Fa endbyte 64*51687Sbostichas a sorting weight of 0. 6548350Scael.Pp 6648350ScaelThe 6748350Scael.Fn radixsort 6848350Scaelfunction 6945286Sbosticis stable, that is, if two elements compare as equal, their order in 7045286Sbosticthe sorted array is unchanged. 7148350Scael.Pp 7248350ScaelThe 7348350Scael.Fn radixsort 7448350Scaelfunction 7545565Sbosticis a variant of most-significant-byte radix sorting; in particular, see 7645565SbosticD.E. Knuth's Algorithm R and section 5.2.5, exercise 10. 7748350ScaelThe 7848350Scael.Fn radixsort 7948350Scaelfunction 8045286Sbostictakes linear time relative to the number of bytes in the strings. 8148350Scael.Sh RETURN VALUES 8245286SbosticUpon successful completion 0 is returned. 8345286SbosticOtherwise, \-1 is returned and the global variable 8448350Scael.Va errno 8545286Sbosticis set to indicate the error. 8648350Scael.Sh ERRORS 87*51687Sbostic.Bl -tag -width Er 88*51687Sbostic.It Bq Er EINVAL 89*51687SbosticThe value of the 90*51687Sbostic.Fa endbyte 91*51687Sbosticelement of 92*51687Sbostic.Fa table 93*51687Sbosticis not 0 or 255. 94*51687Sbostic.El 95*51687Sbostic.Pp 96*51687SbosticAdditionally, the 9748350Scael.Fn radixsort 9848350Scaelfunction 9945286Sbosticmay fail and set 10048350Scael.Va errno 10145286Sbosticfor any of the errors specified for the library routine 10248350Scael.Xr malloc 3 . 10348350Scael.Sh SEE ALSO 10448350Scael.Xr sort 1 , 10548350Scael.Xr qsort 3 10648350Scael.Pp 10748350Scael.Rs 10848350Scael.%A Knuth, D.E. 10948350Scael.%D 1968 11048350Scael.%B "The Art of Computer Programming" 11148350Scael.%T "Sorting and Searching" 11248350Scael.%V Vol. 3 11348350Scael.%P pp. 170-178 11448350Scael.Re 11548350Scael.Rs 11648350Scael.%A Paige, R. 11748350Scael.%D 1987 11848350Scael.%T "Three Partition Refinement Algorithms" 11948350Scael.%J "SIAM J. Comput." 12048350Scael.%V Vol. 16 12148350Scael.%N No. 6 12248350Scael.Re 12348350Scael.Sh HISTORY 12448350ScaelThe 12548350Scael.Fn radixsort 12648350Scaelfunction is 12748350Scael.Ud . 128