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.6 (Berkeley) 07/23/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 modified 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. 51More than one byte may have the same sort weight. 52The 53.Fa table 54argument 55is useful for applications which wish to sort different characters 56equally; for example, providing a table with the same weights 57for A-Z as for a-z will result in a case-insensitive sort. 58.Pp 59The 60.Fn radixsort 61function 62is stable, that is, if two elements compare as equal, their order in 63the sorted array is unchanged. 64.Pp 65The 66.Fn radixsort 67function 68is a variant of most-significant-byte radix sorting; in particular, see 69D.E. Knuth's Algorithm R and section 5.2.5, exercise 10. 70The 71.Fn radixsort 72function 73takes linear time relative to the number of bytes in the strings. 74.Sh RETURN VALUES 75Upon successful completion 0 is returned. 76Otherwise, \-1 is returned and the global variable 77.Va errno 78is set to indicate the error. 79.Sh ERRORS 80The 81.Fn radixsort 82function 83may fail and set 84.Va errno 85for any of the errors specified for the library routine 86.Xr malloc 3 . 87.Sh SEE ALSO 88.Xr sort 1 , 89.Xr qsort 3 90.Pp 91.Rs 92.%A Knuth, D.E. 93.%D 1968 94.%B "The Art of Computer Programming" 95.%T "Sorting and Searching" 96.%V Vol. 3 97.%P pp. 170-178 98.Re 99.Rs 100.%A Paige, R. 101.%D 1987 102.%T "Three Partition Refinement Algorithms" 103.%J "SIAM J. Comput." 104.%V Vol. 16 105.%N No. 6 106.Re 107.Sh HISTORY 108The 109.Fn radixsort 110function is 111.Ud . 112.Sh BUGS 113The 114.Fa nmemb 115argument 116must be less than the maximum integer, 117.Dv INT_MAX . 118