148350Scael.\" Copyright (c) 1990, 1991 The Regents of the University of California. 242127Sbostic.\" All rights reserved. 320442Smckusick.\" 4*50315Sbostic.\" This code is derived from software contributed to Berkeley by 5*50315Sbostic.\" the American National Standards Committee X3, on Information 6*50315Sbostic.\" Processing Systems. 7*50315Sbostic.\" 842127Sbostic.\" %sccs.include.redist.man% 920442Smckusick.\" 10*50315Sbostic.\" @(#)qsort.3 6.7 (Berkeley) 06/29/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 8249990Sbosticis that it uses no additional memory. 8348350Scael.Sh RETURN VALUES 8448350ScaelThe 8548350Scael.Fn qsort 8648350Scaelfunction 8745643Sbosticreturns no value. 8849990Sbostic.Pp 8949990SbosticUpon successful completion, 9049990Sbostic.Fn heapsort 9149990Sbosticreturns 0. 9249990SbosticOtherwise, it returns \-1 and the global variable 9349990Sbostic.Va errno 9449990Sbosticis set to indicate the error. 9549990Sbostic.Sh ERRORS 9649990SbosticThe 9749990Sbostic.Fn heapsort 9849990Sbosticfunction succeeds unless: 9949990Sbostic.Bl -tag -width Er 10049990Sbostic.It Bq Er EINVAL 10149990SbosticThe 10249990Sbostic.Fa size 10349990Sbosticargument is zero. 10448350Scael.Sh COMPATIBILITY 10545643SbosticPrevious versions of 10648350Scael.Fn qsort 10745643Sbosticdid not permit the comparison routine to itself call 10848350Scael.Fn qsort 3 . 10945643SbosticThis is no longer true. 11048350Scael.Sh SEE ALSO 11148350Scael.Xr sort 1 , 11248350Scael.Xr radixsort 3 11348350Scael.Rs 11448350Scael.%A Hoare, C.A.R. 11548350Scael.%D 1962 11648350Scael.%T "Quicksort" 11748350Scael.%J "The Computer Journal" 11848350Scael.%V 5:1 11948350Scael.%P pp. 10-15 12048350Scael.Re 12148350Scael.Rs 12249990Sbostic.%A Williams, J.W.J 12349990Sbostic.%D 1964 12449990Sbostic.%T "Heapsort" 12549990Sbostic.%J "Communications of the ACM" 12649990Sbostic.%V 7:1 12749990Sbostic.%P pp. 347-348 12849990Sbostic.Re 12949990Sbostic.Rs 13048350Scael.%A Knuth, D.E. 13148350Scael.%D 1968 13248350Scael.%B "The Art of Computer Programming" 13348350Scael.%V Vol. 3 13448350Scael.%T "Sorting and Searching" 13549990Sbostic.%P pp. 114-123, 145-149 13648350Scael.Re 13748350Scael.Sh STANDARDS 13848350ScaelThe 13948350Scael.Fn qsort 14048350Scaelfunction 14148350Scaelconforms to 14248350Scael.St -ansiC . 143