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.5 (Berkeley) 04/19/91 7.\" 8.Dd 9.Dt QSORT 3 10.Os 11.Sh NAME 12.Nm qsort 13.Nd quicker sort 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.Sh DESCRIPTION 19The 20.Fn qsort 21function 22is a modified partition-exchange sort, or quicksort. 23.Pp 24The 25.Fn qsort 26function sorts an array of 27.Fa nmemb 28objects, the initial member of which is pointed to by 29.Fa base . 30The size of each object is specified by 31.Fa size . 32.Pp 33The contents of the array are sorted in ascending order according to 34a comparison function pointed to by 35.Fa compar , 36which is called with two arguments that point to the objects being 37compared. 38.Pp 39The comparison function must return an integer less than, equal to, or 40greater than zero if the first argument is considered to be respectively 41less than, equal to, or greater than the second. 42.Pp 43The 44.Fn qsort 45function 46is 47.Em not 48stable, that is, if two members compare as equal, their order in 49the sorted array is undefined. 50.Pp 51The 52.Fn qsort 53function 54is an implementation of C.A.R. Hoare's ``quicksort'' algorithm, a variant 55of partition-exchange sorting; in particular, see D.E. Knuth's Algorithm Q. 56.Fn Qsort 57takes O N lg N average time. 58.Sh RETURN VALUES 59The 60.Fn qsort 61function 62returns no value. 63.Sh COMPATIBILITY 64Previous versions of 65.Fn qsort 66did not permit the comparison routine to itself call 67.Fn qsort 3 . 68This is no longer true. 69.Sh SEE ALSO 70.Xr sort 1 , 71.Xr radixsort 3 72.Rs 73.%A Hoare, C.A.R. 74.%D 1962 75.%T "Quicksort" 76.%J "The Computer Journal" 77.%V 5:1 78.%P pp. 10-15 79.Re 80.Rs 81.%A Knuth, D.E. 82.%D 1968 83.%B "The Art of Computer Programming" 84.%V Vol. 3 85.%T "Sorting and Searching" 86.%P pp. 114-123 87.Re 88.Sh STANDARDS 89The 90.Fn qsort 91function 92conforms to 93.St -ansiC . 94