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