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