1.\" Copyright (c) 1990, 1991 The Regents of the University of California. 2.\" All rights reserved. 3.\" 4.\" This code is derived from software contributed to Berkeley by 5.\" the American National Standards Committee X3, on Information 6.\" Processing Systems. 7.\" 8.\" %sccs.include.redist.man% 9.\" 10.\" @(#)qsort.3 6.8 (Berkeley) 09/23/91 11.\" 12.Dd 13.Dt QSORT 3 14.Os 15.Sh NAME 16.Nm qsort, heapsort 17.Nd sort functions 18.Sh SYNOPSIS 19.Fd #include <stdlib.h> 20.Ft void 21.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 22.Ft int 23.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 24.Sh DESCRIPTION 25The 26.Fn qsort 27function is a modified partition-exchange sort, or quicksort. 28The 29.Fn heapsort 30function is a modified selection sort. 31.Pp 32The 33.Fn qsort 34and 35.Fn heapsort 36functions sort an array of 37.Fa nmemb 38objects, the initial member of which is pointed to by 39.Fa base . 40The size of each object is specified by 41.Fa size . 42.Pp 43The contents of the array are sorted in ascending order according to 44a comparison function pointed to by 45.Fa compar , 46which is called with two arguments that point to the objects being 47compared. 48.Pp 49The comparison function must return an integer less than, equal to, or 50greater than zero if the first argument is considered to be respectively 51less than, equal to, or greater than the second. 52.Pp 53The functions 54.Fn qsort 55and 56.Fn heapsort 57are 58.Em not 59stable, that is, if two members compare as equal, their order in 60the sorted array is undefined. 61.Pp 62The 63.Fn qsort 64function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm, 65a variant of partition-exchange sorting; in particular, see D.E. Knuth's 66Algorithm Q. 67.Fn Qsort 68takes O N lg N average time. 69This implementation uses median selection to avoid the traditional 70O N**2 worst-case behavior. 71.Pp 72The 73.Fn heapsort 74function is an implementation of J.W.J. William's ``heapsort'' algorithm, 75a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. 76.Fn Heapsort 77takes O N lg N worst-case time. 78Its 79.Em only 80advantage over 81.Fn qsort 82is that it uses almost no additional memory; while 83.Nm qsort 84does not allocate memory, it is implemented using recursion. 85.Sh RETURN VALUES 86The 87.Fn qsort 88function 89returns no value. 90.Pp 91Upon successful completion, 92.Fn heapsort 93returns 0. 94Otherwise, it returns \-1 and the global variable 95.Va errno 96is set to indicate the error. 97.Sh ERRORS 98The 99.Fn heapsort 100function succeeds unless: 101.Bl -tag -width Er 102.It Bq Er EINVAL 103The 104.Fa size 105argument is zero. 106.It Bq Er ENOMEM 107.Nm Heapsort 108failed because it was unable to allocate memory. 109.Sh COMPATIBILITY 110Previous versions of 111.Fn qsort 112did not permit the comparison routine to itself call 113.Fn qsort 3 . 114This is no longer true. 115.Sh SEE ALSO 116.Xr sort 1 , 117.Xr radixsort 3 118.Rs 119.%A Hoare, C.A.R. 120.%D 1962 121.%T "Quicksort" 122.%J "The Computer Journal" 123.%V 5:1 124.%P pp. 10-15 125.Re 126.Rs 127.%A Williams, J.W.J 128.%D 1964 129.%T "Heapsort" 130.%J "Communications of the ACM" 131.%V 7:1 132.%P pp. 347-348 133.Re 134.Rs 135.%A Knuth, D.E. 136.%D 1968 137.%B "The Art of Computer Programming" 138.%V Vol. 3 139.%T "Sorting and Searching" 140.%P pp. 114-123, 145-149 141.Re 142.Sh STANDARDS 143The 144.Fn qsort 145function 146conforms to 147.St -ansiC . 148