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.7 (Berkeley) 06/29/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 no additional memory. 83.Sh RETURN VALUES 84The 85.Fn qsort 86function 87returns no value. 88.Pp 89Upon successful completion, 90.Fn heapsort 91returns 0. 92Otherwise, it returns \-1 and the global variable 93.Va errno 94is set to indicate the error. 95.Sh ERRORS 96The 97.Fn heapsort 98function succeeds unless: 99.Bl -tag -width Er 100.It Bq Er EINVAL 101The 102.Fa size 103argument is zero. 104.Sh COMPATIBILITY 105Previous versions of 106.Fn qsort 107did not permit the comparison routine to itself call 108.Fn qsort 3 . 109This is no longer true. 110.Sh SEE ALSO 111.Xr sort 1 , 112.Xr radixsort 3 113.Rs 114.%A Hoare, C.A.R. 115.%D 1962 116.%T "Quicksort" 117.%J "The Computer Journal" 118.%V 5:1 119.%P pp. 10-15 120.Re 121.Rs 122.%A Williams, J.W.J 123.%D 1964 124.%T "Heapsort" 125.%J "Communications of the ACM" 126.%V 7:1 127.%P pp. 347-348 128.Re 129.Rs 130.%A Knuth, D.E. 131.%D 1968 132.%B "The Art of Computer Programming" 133.%V Vol. 3 134.%T "Sorting and Searching" 135.%P pp. 114-123, 145-149 136.Re 137.Sh STANDARDS 138The 139.Fn qsort 140function 141conforms to 142.St -ansiC . 143