148350Scael.\" Copyright (c) 1990, 1991 The Regents of the University of California. 242127Sbostic.\" All rights reserved. 320442Smckusick.\" 442127Sbostic.\" %sccs.include.redist.man% 520442Smckusick.\" 6*49990Sbostic.\" @(#)qsort.3 6.6 (Berkeley) 06/04/91 742127Sbostic.\" 848350Scael.Dd 948350Scael.Dt QSORT 3 1048350Scael.Os 1148350Scael.Sh NAME 12*49990Sbostic.Nm qsort, heapsort 13*49990Sbostic.Nd sort functions 1448350Scael.Sh SYNOPSIS 1548350Scael.Fd #include <stdlib.h> 1648350Scael.Ft void 1748350Scael.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 18*49990Sbostic.Ft int 19*49990Sbostic.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 2048350Scael.Sh DESCRIPTION 2148350ScaelThe 2248350Scael.Fn qsort 23*49990Sbosticfunction is a modified partition-exchange sort, or quicksort. 24*49990SbosticThe 25*49990Sbostic.Fn heapsort 26*49990Sbosticfunction is a modified selection sort. 2748350Scael.Pp 2842127SbosticThe 2948350Scael.Fn qsort 30*49990Sbosticand 31*49990Sbostic.Fn heapsort 32*49990Sbosticfunctions sort an array of 3348350Scael.Fa nmemb 3442127Sbosticobjects, the initial member of which is pointed to by 3548350Scael.Fa base . 3642127SbosticThe size of each object is specified by 3748350Scael.Fa size . 3848350Scael.Pp 3942127SbosticThe contents of the array are sorted in ascending order according to 4042127Sbostica comparison function pointed to by 4148350Scael.Fa compar , 4242127Sbosticwhich is called with two arguments that point to the objects being 4342127Sbosticcompared. 4448350Scael.Pp 4542127SbosticThe comparison function must return an integer less than, equal to, or 4642127Sbosticgreater than zero if the first argument is considered to be respectively 4720442Smckusickless than, equal to, or greater than the second. 4848350Scael.Pp 49*49990SbosticThe functions 5048350Scael.Fn qsort 51*49990Sbosticand 52*49990Sbostic.Fn heapsort 53*49990Sbosticare 5448350Scael.Em not 5545643Sbosticstable, that is, if two members compare as equal, their order in 5645643Sbosticthe sorted array is undefined. 5748350Scael.Pp 5848350ScaelThe 5948350Scael.Fn qsort 60*49990Sbosticfunction is an implementation of C.A.R. Hoare's ``quicksort'' algorithm, 61*49990Sbostica variant of partition-exchange sorting; in particular, see D.E. Knuth's 62*49990SbosticAlgorithm Q. 6348350Scael.Fn Qsort 6445643Sbostictakes O N lg N average time. 65*49990SbosticThis implementation uses median selection to avoid the traditional 66*49990SbosticO N**2 worst-case behavior. 67*49990Sbostic.Pp 68*49990SbosticThe 69*49990Sbostic.Fn heapsort 70*49990Sbosticfunction is an implementation of J.W.J. William's ``heapsort'' algorithm, 71*49990Sbostica variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. 72*49990Sbostic.Fn Heapsort 73*49990Sbostictakes O N lg N worst-case time. 74*49990SbosticIts 75*49990Sbostic.Em only 76*49990Sbosticadvantage over 77*49990Sbostic.Fn qsort 78*49990Sbosticis that it uses no additional memory. 7948350Scael.Sh RETURN VALUES 8048350ScaelThe 8148350Scael.Fn qsort 8248350Scaelfunction 8345643Sbosticreturns no value. 84*49990Sbostic.Pp 85*49990SbosticUpon successful completion, 86*49990Sbostic.Fn heapsort 87*49990Sbosticreturns 0. 88*49990SbosticOtherwise, it returns \-1 and the global variable 89*49990Sbostic.Va errno 90*49990Sbosticis set to indicate the error. 91*49990Sbostic.Sh ERRORS 92*49990SbosticThe 93*49990Sbostic.Fn heapsort 94*49990Sbosticfunction succeeds unless: 95*49990Sbostic.Bl -tag -width Er 96*49990Sbostic.It Bq Er EINVAL 97*49990SbosticThe 98*49990Sbostic.Fa size 99*49990Sbosticargument is zero. 10048350Scael.Sh COMPATIBILITY 10145643SbosticPrevious versions of 10248350Scael.Fn qsort 10345643Sbosticdid not permit the comparison routine to itself call 10448350Scael.Fn qsort 3 . 10545643SbosticThis is no longer true. 10648350Scael.Sh SEE ALSO 10748350Scael.Xr sort 1 , 10848350Scael.Xr radixsort 3 10948350Scael.Rs 11048350Scael.%A Hoare, C.A.R. 11148350Scael.%D 1962 11248350Scael.%T "Quicksort" 11348350Scael.%J "The Computer Journal" 11448350Scael.%V 5:1 11548350Scael.%P pp. 10-15 11648350Scael.Re 11748350Scael.Rs 118*49990Sbostic.%A Williams, J.W.J 119*49990Sbostic.%D 1964 120*49990Sbostic.%T "Heapsort" 121*49990Sbostic.%J "Communications of the ACM" 122*49990Sbostic.%V 7:1 123*49990Sbostic.%P pp. 347-348 124*49990Sbostic.Re 125*49990Sbostic.Rs 12648350Scael.%A Knuth, D.E. 12748350Scael.%D 1968 12848350Scael.%B "The Art of Computer Programming" 12948350Scael.%V Vol. 3 13048350Scael.%T "Sorting and Searching" 131*49990Sbostic.%P pp. 114-123, 145-149 13248350Scael.Re 13348350Scael.Sh STANDARDS 13448350ScaelThe 13548350Scael.Fn qsort 13648350Scaelfunction 13748350Scaelconforms to 13848350Scael.St -ansiC . 139