148350Scael.\" Copyright (c) 1990, 1991 The Regents of the University of California. 245286Sbostic.\" All rights reserved. 345286Sbostic.\" 445286Sbostic.\" %sccs.include.redist.man% 545286Sbostic.\" 6*54579Sbostic.\" @(#)radixsort.3 5.9 (Berkeley) 06/30/92 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" 19*54579Sbostic.Ft int 20*54579Sbostic.Fn sradixsort "u_char **base" "int nmemb" "u_char *table" "u_int endbyte" 2148350Scael.Sh DESCRIPTION 2248350ScaelThe 2348350Scael.Fn radixsort 24*54579Sbosticand 25*54579Sbostic.Fn sradixsort 26*54579Sbosticfunctions 27*54579Sbosticare implementations of radix sort. 2848350Scael.Pp 29*54579SbosticThese functions sort an array of pointers to byte strings, the initial 30*54579Sbosticmember of which is referenced by 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 . 3548350Scael.Pp 3645286SbosticApplications may specify a sort order by providing the 3748350Scael.Fa table 3845286Sbosticargument. 3948350ScaelIf 4048350Scael.Pf non- Dv NULL , 4148350Scael.Fa table 4248350Scaelmust reference an array of 4348350Scael.Dv UCHAR_MAX 4448350Scael+ 1 bytes which contains the sort 4545427Sbosticweight of each possible byte value. 4651687SbosticThe end-of-string byte must have a sort weight of 0 or 255 4751687Sbostic(for sorting in reverse order). 4845286SbosticMore than one byte may have the same sort weight. 4948350ScaelThe 5048350Scael.Fa table 5148350Scaelargument 5245286Sbosticis useful for applications which wish to sort different characters 53*54579Sbosticequally, for example, providing a table with the same weights 5445286Sbosticfor A-Z as for a-z will result in a case-insensitive sort. 5551687SbosticIf 5651687Sbostic.Fa table 57*54579Sbosticis NULL, the contents of the array are sorted in ascending order 58*54579Sbosticaccording to the 59*54579Sbostic.Tn ASCII 60*54579Sbosticorder of the byte strings they reference and 6151687Sbostic.Fa endbyte 6251687Sbostichas a sorting weight of 0. 6348350Scael.Pp 6448350ScaelThe 65*54579Sbostic.Fn sradixsort 66*54579Sbosticfunction is stable, that is, if two elements compare as equal, their 67*54579Sbosticorder in the sorted array is unchanged. 68*54579SbosticThe 69*54579Sbostic.Fn sradixsort 70*54579Sbosticfunction uses additional memory sufficient to hold 71*54579Sbostic.Fa nmemb 72*54579Sbosticpointers. 7348350Scael.Pp 7448350ScaelThe 7548350Scael.Fn radixsort 76*54579Sbosticfunction is not stable, but uses no additional memory. 77*54579Sbostic.Pp 78*54579SbosticThese functions are variants of most-significant-byte radix sorting; in 79*54579Sbosticparticular, see D.E. Knuth's Algorithm R and section 5.2.5, exercise 10. 80*54579SbosticThey take 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 8751687Sbostic.Bl -tag -width Er 8851687Sbostic.It Bq Er EINVAL 8951687SbosticThe value of the 9051687Sbostic.Fa endbyte 9151687Sbosticelement of 9251687Sbostic.Fa table 9351687Sbosticis not 0 or 255. 9451687Sbostic.El 9551687Sbostic.Pp 9651687SbosticAdditionally, the 97*54579Sbostic.Fn sradixsort 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