1*61180Sbostic.\" Copyright (c) 1990, 1991, 1993 2*61180Sbostic.\" The Regents of the University of California. 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*61180Sbostic.\" @(#)qsort.3 8.1 (Berkeley) 06/04/93 1142127Sbostic.\" 1248350Scael.Dd 1348350Scael.Dt QSORT 3 1448350Scael.Os 1548350Scael.Sh NAME 1656965Sbostic.Nm qsort, heapsort, mergesort 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 *)" 2456965Sbostic.Ft int 2556965Sbostic.Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 2648350Scael.Sh DESCRIPTION 2748350ScaelThe 2848350Scael.Fn qsort 2949990Sbosticfunction is a modified partition-exchange sort, or quicksort. 3049990SbosticThe 3149990Sbostic.Fn heapsort 3249990Sbosticfunction is a modified selection sort. 3356965SbosticThe 3456965Sbostic.Fn mergesort 3556965Sbosticfunction is a modified merge sort with exponential search 3656965Sbosticintended for sorting data with pre-existing order. 3748350Scael.Pp 3842127SbosticThe 3948350Scael.Fn qsort 4049990Sbosticand 4149990Sbostic.Fn heapsort 4249990Sbosticfunctions sort an array of 4348350Scael.Fa nmemb 4442127Sbosticobjects, the initial member of which is pointed to by 4548350Scael.Fa base . 4642127SbosticThe size of each object is specified by 4748350Scael.Fa size . 4856965Sbostic.Fn Mergesort 4956965Sbosticbehaves similarly, but 5056965Sbostic.Em requires 5156965Sbosticthat 5256965Sbostic.Fa size 5356965Sbosticbe greater than 5456965Sbostic.Dq "sizeof(void *) / 2" . 5548350Scael.Pp 5656965SbosticThe contents of the array 5756965Sbostic.Fa base 5856965Sbosticare sorted in ascending order according to 5942127Sbostica comparison function pointed to by 6048350Scael.Fa compar , 6156965Sbosticwhich requires two arguments pointing to the objects being 6242127Sbosticcompared. 6348350Scael.Pp 6442127SbosticThe comparison function must return an integer less than, equal to, or 6542127Sbosticgreater than zero if the first argument is considered to be respectively 6620442Smckusickless than, equal to, or greater than the second. 6748350Scael.Pp 6849990SbosticThe functions 6948350Scael.Fn qsort 7049990Sbosticand 7149990Sbostic.Fn heapsort 7249990Sbosticare 7348350Scael.Em not 7445643Sbosticstable, that is, if two members compare as equal, their order in 7545643Sbosticthe sorted array is undefined. 7656965SbosticThe function 7756965Sbostic.Fn mergesort 7856965Sbosticis stable. 7948350Scael.Pp 8048350ScaelThe 8148350Scael.Fn qsort 8249990Sbosticfunction is an implementation of C.A.R. Hoare's ``quicksort'' algorithm, 8349990Sbostica variant of partition-exchange sorting; in particular, see D.E. Knuth's 8449990SbosticAlgorithm Q. 8548350Scael.Fn Qsort 8645643Sbostictakes O N lg N average time. 8756965SbosticThis implementation uses median selection to avoid its 8849990SbosticO N**2 worst-case behavior. 8949990Sbostic.Pp 9049990SbosticThe 9149990Sbostic.Fn heapsort 9249990Sbosticfunction is an implementation of J.W.J. William's ``heapsort'' algorithm, 9349990Sbostica variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. 9449990Sbostic.Fn Heapsort 9549990Sbostictakes O N lg N worst-case time. 9649990SbosticIts 9749990Sbostic.Em only 9849990Sbosticadvantage over 9949990Sbostic.Fn qsort 10051175Sbosticis that it uses almost no additional memory; while 10156965Sbostic.Fn qsort 10251175Sbosticdoes not allocate memory, it is implemented using recursion. 10356965Sbostic.Pp 10456965SbosticThe function 10556965Sbostic.Fn mergesort 10656965Sbosticrequires additional memory of size 10756965Sbostic.Fa nmemb * 10856965Sbostic.Fa size 10956965Sbosticbytes; it should be used only when space is not at a premium. 11056965Sbostic.Fn Mergesort 11156965Sbosticis optimized for data with pre-existing order; its worst case 11256965Sbostictime is O N lg N; its best case is O N. 11356965Sbostic.Pp 11456965SbosticNormally, 11556965Sbostic.Fn qsort 11656965Sbosticis faster than 11756965Sbostic.Fn mergesort 11856965Sbosticis faster than 11956965Sbostic.Fn heapsort . 12056965SbosticMemory availability and pre-existing order in the data can make this 12156965Sbosticuntrue. 12248350Scael.Sh RETURN VALUES 12348350ScaelThe 12448350Scael.Fn qsort 12548350Scaelfunction 12645643Sbosticreturns no value. 12749990Sbostic.Pp 12849990SbosticUpon successful completion, 12949990Sbostic.Fn heapsort 13056965Sbosticand 13156965Sbostic.Fn mergesort 13256965Sbosticreturn 0. 13356965SbosticOtherwise, they return \-1 and the global variable 13449990Sbostic.Va errno 13549990Sbosticis set to indicate the error. 13649990Sbostic.Sh ERRORS 13749990SbosticThe 13849990Sbostic.Fn heapsort 13949990Sbosticfunction succeeds unless: 14049990Sbostic.Bl -tag -width Er 14149990Sbostic.It Bq Er EINVAL 14249990SbosticThe 14349990Sbostic.Fa size 14456965Sbosticargument is zero, or, 14556965Sbosticthe 14656965Sbostic.Fa size 14756965Sbosticargument to 14856965Sbostic.Fn mergesort 14956965Sbosticis less than 15056965Sbostic.Dq "sizeof(void *) / 2" . 15151175Sbostic.It Bq Er ENOMEM 15256965Sbostic.Fn Heapsort 15356965Sbosticor 15456965Sbostic.Fn mergesort 15556965Sbosticwere unable to allocate memory. 15656965Sbostic.El 15748350Scael.Sh COMPATIBILITY 15845643SbosticPrevious versions of 15948350Scael.Fn qsort 16056965Sbosticdid not permit the comparison routine itself to call 16148350Scael.Fn qsort 3 . 16245643SbosticThis is no longer true. 16348350Scael.Sh SEE ALSO 16448350Scael.Xr sort 1 , 16548350Scael.Xr radixsort 3 16648350Scael.Rs 16748350Scael.%A Hoare, C.A.R. 16848350Scael.%D 1962 16948350Scael.%T "Quicksort" 17048350Scael.%J "The Computer Journal" 17148350Scael.%V 5:1 17248350Scael.%P pp. 10-15 17348350Scael.Re 17459103Sbostic.Rs 17549990Sbostic.%A Williams, J.W.J 17649990Sbostic.%D 1964 17749990Sbostic.%T "Heapsort" 17849990Sbostic.%J "Communications of the ACM" 17949990Sbostic.%V 7:1 18049990Sbostic.%P pp. 347-348 18149990Sbostic.Re 18249990Sbostic.Rs 18348350Scael.%A Knuth, D.E. 18448350Scael.%D 1968 18548350Scael.%B "The Art of Computer Programming" 18648350Scael.%V Vol. 3 18748350Scael.%T "Sorting and Searching" 18849990Sbostic.%P pp. 114-123, 145-149 18948350Scael.Re 19056965Sbostic.Rs 19156965Sbostic.%A Mcilroy, P.M. 19256965Sbostic.%T "Optimistic Sorting and Information Theoretic Complexity" 19356965Sbostic.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms" 19456965Sbostic.%V January 1992 19556965Sbostic.Re 19657429Sbostic.Rs 19757429Sbostic.%A Bentley, J.L. 19857429Sbostic.%T "Engineering a Sort Function" 19957429Sbostic.%J "bentley@research.att.com" 20057429Sbostic.%V January 1992 20157429Sbostic.Re 20248350Scael.Sh STANDARDS 20348350ScaelThe 20448350Scael.Fn qsort 20548350Scaelfunction 20648350Scaelconforms to 20748350Scael.St -ansiC . 208