148350Scael.\" Copyright (c) 1990, 1991 The Regents of the University of California. 242127Sbostic.\" All rights reserved. 320442Smckusick.\" 450315Sbostic.\" This code is derived from software contributed to Berkeley by 550315Sbostic.\" the American National Standards Committee X3, on Information 650315Sbostic.\" Processing Systems. 750315Sbostic.\" 842127Sbostic.\" %sccs.include.redist.man% 920442Smckusick.\" 10*51175Sbostic.\" @(#)qsort.3 6.8 (Berkeley) 09/23/91 1142127Sbostic.\" 1248350Scael.Dd 1348350Scael.Dt QSORT 3 1448350Scael.Os 1548350Scael.Sh NAME 1649990Sbostic.Nm qsort, heapsort 1749990Sbostic.Nd sort functions 1848350Scael.Sh SYNOPSIS 1948350Scael.Fd #include <stdlib.h> 2048350Scael.Ft void 2148350Scael.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 2249990Sbostic.Ft int 2349990Sbostic.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 2448350Scael.Sh DESCRIPTION 2548350ScaelThe 2648350Scael.Fn qsort 2749990Sbosticfunction is a modified partition-exchange sort, or quicksort. 2849990SbosticThe 2949990Sbostic.Fn heapsort 3049990Sbosticfunction is a modified selection sort. 3148350Scael.Pp 3242127SbosticThe 3348350Scael.Fn qsort 3449990Sbosticand 3549990Sbostic.Fn heapsort 3649990Sbosticfunctions sort an array of 3748350Scael.Fa nmemb 3842127Sbosticobjects, the initial member of which is pointed to by 3948350Scael.Fa base . 4042127SbosticThe size of each object is specified by 4148350Scael.Fa size . 4248350Scael.Pp 4342127SbosticThe contents of the array are sorted in ascending order according to 4442127Sbostica comparison function pointed to by 4548350Scael.Fa compar , 4642127Sbosticwhich is called with two arguments that point to the objects being 4742127Sbosticcompared. 4848350Scael.Pp 4942127SbosticThe comparison function must return an integer less than, equal to, or 5042127Sbosticgreater than zero if the first argument is considered to be respectively 5120442Smckusickless than, equal to, or greater than the second. 5248350Scael.Pp 5349990SbosticThe functions 5448350Scael.Fn qsort 5549990Sbosticand 5649990Sbostic.Fn heapsort 5749990Sbosticare 5848350Scael.Em not 5945643Sbosticstable, that is, if two members compare as equal, their order in 6045643Sbosticthe sorted array is undefined. 6148350Scael.Pp 6248350ScaelThe 6348350Scael.Fn qsort 6449990Sbosticfunction is an implementation of C.A.R. Hoare's ``quicksort'' algorithm, 6549990Sbostica variant of partition-exchange sorting; in particular, see D.E. Knuth's 6649990SbosticAlgorithm Q. 6748350Scael.Fn Qsort 6845643Sbostictakes O N lg N average time. 6949990SbosticThis implementation uses median selection to avoid the traditional 7049990SbosticO N**2 worst-case behavior. 7149990Sbostic.Pp 7249990SbosticThe 7349990Sbostic.Fn heapsort 7449990Sbosticfunction is an implementation of J.W.J. William's ``heapsort'' algorithm, 7549990Sbostica variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. 7649990Sbostic.Fn Heapsort 7749990Sbostictakes O N lg N worst-case time. 7849990SbosticIts 7949990Sbostic.Em only 8049990Sbosticadvantage over 8149990Sbostic.Fn qsort 82*51175Sbosticis that it uses almost no additional memory; while 83*51175Sbostic.Nm qsort 84*51175Sbosticdoes not allocate memory, it is implemented using recursion. 8548350Scael.Sh RETURN VALUES 8648350ScaelThe 8748350Scael.Fn qsort 8848350Scaelfunction 8945643Sbosticreturns no value. 9049990Sbostic.Pp 9149990SbosticUpon successful completion, 9249990Sbostic.Fn heapsort 9349990Sbosticreturns 0. 9449990SbosticOtherwise, it returns \-1 and the global variable 9549990Sbostic.Va errno 9649990Sbosticis set to indicate the error. 9749990Sbostic.Sh ERRORS 9849990SbosticThe 9949990Sbostic.Fn heapsort 10049990Sbosticfunction succeeds unless: 10149990Sbostic.Bl -tag -width Er 10249990Sbostic.It Bq Er EINVAL 10349990SbosticThe 10449990Sbostic.Fa size 10549990Sbosticargument is zero. 106*51175Sbostic.It Bq Er ENOMEM 107*51175Sbostic.Nm Heapsort 108*51175Sbosticfailed because it was unable to allocate memory. 10948350Scael.Sh COMPATIBILITY 11045643SbosticPrevious versions of 11148350Scael.Fn qsort 11245643Sbosticdid not permit the comparison routine to itself call 11348350Scael.Fn qsort 3 . 11445643SbosticThis is no longer true. 11548350Scael.Sh SEE ALSO 11648350Scael.Xr sort 1 , 11748350Scael.Xr radixsort 3 11848350Scael.Rs 11948350Scael.%A Hoare, C.A.R. 12048350Scael.%D 1962 12148350Scael.%T "Quicksort" 12248350Scael.%J "The Computer Journal" 12348350Scael.%V 5:1 12448350Scael.%P pp. 10-15 12548350Scael.Re 12648350Scael.Rs 12749990Sbostic.%A Williams, J.W.J 12849990Sbostic.%D 1964 12949990Sbostic.%T "Heapsort" 13049990Sbostic.%J "Communications of the ACM" 13149990Sbostic.%V 7:1 13249990Sbostic.%P pp. 347-348 13349990Sbostic.Re 13449990Sbostic.Rs 13548350Scael.%A Knuth, D.E. 13648350Scael.%D 1968 13748350Scael.%B "The Art of Computer Programming" 13848350Scael.%V Vol. 3 13948350Scael.%T "Sorting and Searching" 14049990Sbostic.%P pp. 114-123, 145-149 14148350Scael.Re 14248350Scael.Sh STANDARDS 14348350ScaelThe 14448350Scael.Fn qsort 14548350Scaelfunction 14648350Scaelconforms to 14748350Scael.St -ansiC . 148