1*48350Scael.\" Copyright (c) 1990, 1991 The Regents of the University of California. 242127Sbostic.\" All rights reserved. 320442Smckusick.\" 442127Sbostic.\" %sccs.include.redist.man% 520442Smckusick.\" 6*48350Scael.\" @(#)qsort.3 6.5 (Berkeley) 04/19/91 742127Sbostic.\" 8*48350Scael.Dd 9*48350Scael.Dt QSORT 3 10*48350Scael.Os 11*48350Scael.Sh NAME 12*48350Scael.Nm qsort 13*48350Scael.Nd quicker sort 14*48350Scael.Sh SYNOPSIS 15*48350Scael.Fd #include <stdlib.h> 16*48350Scael.Ft void 17*48350Scael.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 18*48350Scael.Sh DESCRIPTION 19*48350ScaelThe 20*48350Scael.Fn qsort 21*48350Scaelfunction 2245643Sbosticis a modified partition-exchange sort, or quicksort. 23*48350Scael.Pp 2442127SbosticThe 25*48350Scael.Fn qsort 2642127Sbosticfunction sorts an array of 27*48350Scael.Fa nmemb 2842127Sbosticobjects, the initial member of which is pointed to by 29*48350Scael.Fa base . 3042127SbosticThe size of each object is specified by 31*48350Scael.Fa size . 32*48350Scael.Pp 3342127SbosticThe contents of the array are sorted in ascending order according to 3442127Sbostica comparison function pointed to by 35*48350Scael.Fa compar , 3642127Sbosticwhich is called with two arguments that point to the objects being 3742127Sbosticcompared. 38*48350Scael.Pp 3942127SbosticThe comparison function must return an integer less than, equal to, or 4042127Sbosticgreater than zero if the first argument is considered to be respectively 4120442Smckusickless than, equal to, or greater than the second. 42*48350Scael.Pp 43*48350ScaelThe 44*48350Scael.Fn qsort 45*48350Scaelfunction 4645643Sbosticis 47*48350Scael.Em not 4845643Sbosticstable, that is, if two members compare as equal, their order in 4945643Sbosticthe sorted array is undefined. 50*48350Scael.Pp 51*48350ScaelThe 52*48350Scael.Fn qsort 53*48350Scaelfunction 5445643Sbosticis an implementation of C.A.R. Hoare's ``quicksort'' algorithm, a variant 5545643Sbosticof partition-exchange sorting; in particular, see D.E. Knuth's Algorithm Q. 56*48350Scael.Fn Qsort 5745643Sbostictakes O N lg N average time. 58*48350Scael.Sh RETURN VALUES 59*48350ScaelThe 60*48350Scael.Fn qsort 61*48350Scaelfunction 6245643Sbosticreturns no value. 63*48350Scael.Sh COMPATIBILITY 6445643SbosticPrevious versions of 65*48350Scael.Fn qsort 6645643Sbosticdid not permit the comparison routine to itself call 67*48350Scael.Fn qsort 3 . 6845643SbosticThis is no longer true. 69*48350Scael.Sh SEE ALSO 70*48350Scael.Xr sort 1 , 71*48350Scael.Xr radixsort 3 72*48350Scael.Rs 73*48350Scael.%A Hoare, C.A.R. 74*48350Scael.%D 1962 75*48350Scael.%T "Quicksort" 76*48350Scael.%J "The Computer Journal" 77*48350Scael.%V 5:1 78*48350Scael.%P pp. 10-15 79*48350Scael.Re 80*48350Scael.Rs 81*48350Scael.%A Knuth, D.E. 82*48350Scael.%D 1968 83*48350Scael.%B "The Art of Computer Programming" 84*48350Scael.%V Vol. 3 85*48350Scael.%T "Sorting and Searching" 86*48350Scael.%P pp. 114-123 87*48350Scael.Re 88*48350Scael.Sh STANDARDS 89*48350ScaelThe 90*48350Scael.Fn qsort 91*48350Scaelfunction 92*48350Scaelconforms to 93*48350Scael.St -ansiC . 94