1.\" Copyright (c) 1990, 1991 The Regents of the University of California. 2.\" All rights reserved. 3.\" 4.\" %sccs.include.redist.man% 5.\" 6.\" @(#)radixsort.3 5.8 (Berkeley) 11/13/91 7.\" 8.Dd 9.Dt RADIXSORT 3 10.Os 11.Sh NAME 12.Nm radixsort 13.Nd radix sort 14.Sh SYNOPSIS 15.Fd #include <limits.h> 16.Fd #include <stdlib.h> 17.Ft int 18.Fn radixsort "u_char **base" "int nmemb" "u_char *table" "u_int endbyte" 19.Sh DESCRIPTION 20The 21.Fn radixsort 22function 23is a radix sort. 24.Pp 25The 26.Fn radixsort 27function sorts an array of 28.Fa nmemb 29pointers to byte strings, the initial member of which is referenced 30by 31.Fa base . 32The byte strings may contain any values; the end of each string 33is denoted by the user-specified value 34.Fa endbyte . 35The contents of the array are sorted in ascending order according 36to the 37.Tn ASCII 38order of the byte strings they reference. 39.Pp 40Applications may specify a sort order by providing the 41.Fa table 42argument. 43If 44.Pf non- Dv NULL , 45.Fa table 46must reference an array of 47.Dv UCHAR_MAX 48+ 1 bytes which contains the sort 49weight of each possible byte value. 50The end-of-string byte must have a sort weight of 0 or 255 51(for sorting in reverse order). 52More than one byte may have the same sort weight. 53The 54.Fa table 55argument 56is useful for applications which wish to sort different characters 57equally; for example, providing a table with the same weights 58for A-Z as for a-z will result in a case-insensitive sort. 59If 60.Fa table 61is NULL, 62ASCII weights are used and 63.Fa endbyte 64has a sorting weight of 0. 65.Pp 66The 67.Fn radixsort 68function 69is stable, that is, if two elements compare as equal, their order in 70the sorted array is unchanged. 71.Pp 72The 73.Fn radixsort 74function 75is a variant of most-significant-byte radix sorting; in particular, see 76D.E. Knuth's Algorithm R and section 5.2.5, exercise 10. 77The 78.Fn radixsort 79function 80takes linear time relative to the number of bytes in the strings. 81.Sh RETURN VALUES 82Upon successful completion 0 is returned. 83Otherwise, \-1 is returned and the global variable 84.Va errno 85is set to indicate the error. 86.Sh ERRORS 87.Bl -tag -width Er 88.It Bq Er EINVAL 89The value of the 90.Fa endbyte 91element of 92.Fa table 93is not 0 or 255. 94.El 95.Pp 96Additionally, the 97.Fn radixsort 98function 99may fail and set 100.Va errno 101for any of the errors specified for the library routine 102.Xr malloc 3 . 103.Sh SEE ALSO 104.Xr sort 1 , 105.Xr qsort 3 106.Pp 107.Rs 108.%A Knuth, D.E. 109.%D 1968 110.%B "The Art of Computer Programming" 111.%T "Sorting and Searching" 112.%V Vol. 3 113.%P pp. 170-178 114.Re 115.Rs 116.%A Paige, R. 117.%D 1987 118.%T "Three Partition Refinement Algorithms" 119.%J "SIAM J. Comput." 120.%V Vol. 16 121.%N No. 6 122.Re 123.Sh HISTORY 124The 125.Fn radixsort 126function is 127.Ud . 128