xref: /freebsd/lib/libc/stdlib/qsort.3 (revision 9e6482fc5b22b46216ab87af127e989fa60d42fe) 
1.\" Copyright (c) 1990, 1991, 1993
2.\"	The Regents of the University of California.  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.\" Redistribution and use in source and binary forms, with or without
9.\" modification, are permitted provided that the following conditions
10.\" are met:
11.\" 1. Redistributions of source code must retain the above copyright
12.\"    notice, this list of conditions and the following disclaimer.
13.\" 2. Redistributions in binary form must reproduce the above copyright
14.\"    notice, this list of conditions and the following disclaimer in the
15.\"    documentation and/or other materials provided with the distribution.
16.\" 3. All advertising materials mentioning features or use of this software
17.\"    must display the following acknowledgement:
18.\"	This product includes software developed by the University of
19.\"	California, Berkeley and its contributors.
20.\" 4. Neither the name of the University nor the names of its contributors
21.\"    may be used to endorse or promote products derived from this software
22.\"    without specific prior written permission.
23.\"
24.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34.\" SUCH DAMAGE.
35.\"
36.\"     @(#)qsort.3	8.1 (Berkeley) 6/4/93
37.\" $FreeBSD$
38.\"
39.Dd September 7, 2002
40.Dt QSORT 3
41.Os
42.Sh NAME
43.Nm qsort , qsort_r , heapsort , mergesort
44.Nd sort functions
45.Sh LIBRARY
46.Lb libc
47.Sh SYNOPSIS
48.In stdlib.h
49.Ft void
50.Fo qsort
51.Fa "void *base"
52.Fa "size_t nmemb"
53.Fa "size_t size"
54.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
55.Fc
56.Ft void
57.Fo qsort_r
58.Fa "void *base"
59.Fa "size_t nmemb"
60.Fa "size_t size"
61.Fa "void *thunk"
62.Fa "int \*[lp]*compar\*[rp]\*[lp]void *, const void *, const void *\*[rp]"
63.Fc
64.Ft int
65.Fo heapsort
66.Fa "void *base"
67.Fa "size_t nmemb"
68.Fa "size_t size"
69.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
70.Fc
71.Ft int
72.Fo mergesort
73.Fa "void *base"
74.Fa "size_t nmemb"
75.Fa "size_t size"
76.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
77.Fc
78.Sh DESCRIPTION
79The
80.Fn qsort
81function is a modified partition-exchange sort, or quicksort.
82The
83.Fn heapsort
84function is a modified selection sort.
85The
86.Fn mergesort
87function is a modified merge sort with exponential search
88intended for sorting data with pre-existing order.
89.Pp
90The
91.Fn qsort
92and
93.Fn heapsort
94functions sort an array of
95.Fa nmemb
96objects, the initial member of which is pointed to by
97.Fa base .
98The size of each object is specified by
99.Fa size .
100.Fn Mergesort
101behaves similarly, but
102.Em requires
103that
104.Fa size
105be greater than
106.Dq "sizeof(void *) / 2" .
107.Pp
108The contents of the array
109.Fa base
110are sorted in ascending order according to
111a comparison function pointed to by
112.Fa compar ,
113which requires two arguments pointing to the objects being
114compared.
115.Pp
116The comparison function must return an integer less than, equal to, or
117greater than zero if the first argument is considered to be respectively
118less than, equal to, or greater than the second.
119.Pp
120The
121.Fn qsort_r
122function behaves identically to
123.Fn qsort ,
124except that it takes an additional argument,
125.Fa thunk ,
126which is passed unchanged as the first argument to function pointed to
127.Fa compar .
128This allows the comparison function to access additional
129data without using global variables, and thus
130.Fn qsort_r
131is suitable for use in functions which must be reentrant.
132.Pp
133The algorithms implemented by
134.Fn qsort ,
135.Fn qsort_r ,
136and
137.Fn heapsort
138are
139.Em not
140stable, that is, if two members compare as equal, their order in
141the sorted array is undefined.
142The
143.Fn mergesort
144algorithm is stable.
145.Pp
146The
147.Fn qsort
148and
149.Fn qsort_r
150functions are an implementation of C.A.R. Hoare's
151.Dq quicksort
152algorithm,
153a variant of partition-exchange sorting; in particular, see D.E. Knuth's
154Algorithm Q.
155.Sy Quicksort
156takes O N lg N average time.
157This implementation uses median selection to avoid its
158O N**2 worst-case behavior.
159.Pp
160The
161.Fn heapsort
162function is an implementation of J.W.J. William's
163.Dq heapsort
164algorithm,
165a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H.
166.Sy Heapsort
167takes O N lg N worst-case time.
168Its
169.Em only
170advantage over
171.Fn qsort
172is that it uses almost no additional memory; while
173.Fn qsort
174does not allocate memory, it is implemented using recursion.
175.Pp
176The function
177.Fn mergesort
178requires additional memory of size
179.Fa nmemb *
180.Fa size
181bytes; it should be used only when space is not at a premium.
182.Fn Mergesort
183is optimized for data with pre-existing order; its worst case
184time is O N lg N; its best case is O N.
185.Pp
186Normally,
187.Fn qsort
188is faster than
189.Fn mergesort
190is faster than
191.Fn heapsort .
192Memory availability and pre-existing order in the data can make this
193untrue.
194.Sh RETURN VALUES
195The
196.Fn qsort
197and
198.Fn qsort_r
199functions
200return no value.
201.Pp
202.Rv -std heapsort mergesort
203.Sh ERRORS
204The
205.Fn heapsort
206and
207.Fn mergesort
208functions succeed unless:
209.Bl -tag -width Er
210.It Bq Er EINVAL
211The
212.Fa size
213argument is zero, or,
214the
215.Fa size
216argument to
217.Fn mergesort
218is less than
219.Dq "sizeof(void *) / 2" .
220.It Bq Er ENOMEM
221.Fn Heapsort
222or
223.Fn mergesort
224were unable to allocate memory.
225.El
226.Sh COMPATIBILITY
227Previous versions of
228.Fn qsort
229did not permit the comparison routine itself to call
230.Fn qsort 3 .
231This is no longer true.
232.Sh SEE ALSO
233.Xr sort 1 ,
234.Xr radixsort 3
235.Rs
236.%A Hoare, C.A.R.
237.%D 1962
238.%T "Quicksort"
239.%J "The Computer Journal"
240.%V 5:1
241.%P pp. 10-15
242.Re
243.Rs
244.%A Williams, J.W.J
245.%D 1964
246.%T "Heapsort"
247.%J "Communications of the ACM"
248.%V 7:1
249.%P pp. 347-348
250.Re
251.Rs
252.%A Knuth, D.E.
253.%D 1968
254.%B "The Art of Computer Programming"
255.%V Vol. 3
256.%T "Sorting and Searching"
257.%P pp. 114-123, 145-149
258.Re
259.Rs
260.%A Mcilroy, P.M.
261.%T "Optimistic Sorting and Information Theoretic Complexity"
262.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
263.%V January 1992
264.Re
265.Rs
266.%A Bentley, J.L.
267.%T "Engineering a Sort Function"
268.%J "bentley@research.att.com"
269.%V January 1992
270.Re
271.Sh STANDARDS
272The
273.Fn qsort
274function
275conforms to
276.St -isoC .
277