162929Sbostic.\" Copyright (c) 1990, 1991, 1993 262929Sbostic.\" The Regents of the University of California. All rights reserved. 345286Sbostic.\" 445286Sbostic.\" %sccs.include.redist.man% 545286Sbostic.\" 6*65920Sbostic.\" @(#)radixsort.3 8.2 (Berkeley) 01/27/94 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" 1954579Sbostic.Ft int 2054579Sbostic.Fn sradixsort "u_char **base" "int nmemb" "u_char *table" "u_int endbyte" 2148350Scael.Sh DESCRIPTION 2248350ScaelThe 2348350Scael.Fn radixsort 2454579Sbosticand 2554579Sbostic.Fn sradixsort 2654579Sbosticfunctions 2754579Sbosticare implementations of radix sort. 2848350Scael.Pp 2954579SbosticThese functions sort an array of pointers to byte strings, the initial 3054579Sbosticmember 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 5354579Sbosticequally, 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 5754579Sbosticis NULL, the contents of the array are sorted in ascending order 5854579Sbosticaccording to the 5954579Sbostic.Tn ASCII 6054579Sbosticorder of the byte strings they reference and 6151687Sbostic.Fa endbyte 6251687Sbostichas a sorting weight of 0. 6348350Scael.Pp 6448350ScaelThe 6554579Sbostic.Fn sradixsort 6654579Sbosticfunction is stable, that is, if two elements compare as equal, their 6754579Sbosticorder in the sorted array is unchanged. 6854579SbosticThe 6954579Sbostic.Fn sradixsort 7054579Sbosticfunction uses additional memory sufficient to hold 7154579Sbostic.Fa nmemb 7254579Sbosticpointers. 7348350Scael.Pp 7448350ScaelThe 7548350Scael.Fn radixsort 7654579Sbosticfunction is not stable, but uses no additional memory. 7754579Sbostic.Pp 7854579SbosticThese functions are variants of most-significant-byte radix sorting; in 7954579Sbosticparticular, see D.E. Knuth's Algorithm R and section 5.2.5, exercise 10. 8054579SbosticThey 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 9754579Sbostic.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 123*65920Sbostic.Rs 124*65920Sbostic.%A McIlroy, P. 125*65920Sbostic.%D 1993 126*65920Sbostic.%B "Engineering Radix Sort" 127*65920Sbostic.%T "Computing Systems" 128*65920Sbostic.%V Vol. 6:1 129*65920Sbostic.%P pp. 5-27 130*65920Sbostic.Re 13148350Scael.Sh HISTORY 13248350ScaelThe 13348350Scael.Fn radixsort 13462928Sbosticfunction first appeared in 4.4BSD. 135