gdb - Local mods (compile)
[dragonfly.git] / lib / libc / stdlib / qsort.3
CommitLineData
984263bc
MD
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.
dc71b7ab 16.\" 3. Neither the name of the University nor the names of its contributors
984263bc
MD
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
5d0641a4 33.\" $FreeBSD: src/lib/libc/stdlib/qsort.3,v 1.17 2007/01/09 00:28:10 imp Exp $
0b84df5c 34.\" $DragonFly: src/lib/libc/stdlib/qsort.3,v 1.4 2006/02/17 19:35:06 swildner Exp $
984263bc 35.\"
5d0641a4 36.Dd September 30, 2003
984263bc
MD
37.Dt QSORT 3
38.Os
39.Sh NAME
d0de9052 40.Nm qsort ,
5d0641a4 41.Nm qsort_r ,
d0de9052
SW
42.Nm heapsort ,
43.Nm mergesort
984263bc
MD
44.Nd sort functions
45.Sh LIBRARY
46.Lb libc
47.Sh SYNOPSIS
48.In stdlib.h
49.Ft void
5d0641a4
PA
50.Fo qsort
51.Fa "void *base"
52.Fa "size_t nmemb"
53.Fa "size_t size"
25c75583 54.Fa "int (*compar)(const void *, const void *)"
5d0641a4
PA
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"
25c75583 62.Fa "int (*compar)(void *, const void *, const void *)"
5d0641a4 63.Fc
984263bc 64.Ft int
5d0641a4
PA
65.Fo heapsort
66.Fa "void *base"
67.Fa "size_t nmemb"
68.Fa "size_t size"
25c75583 69.Fa "int (*compar)(const void *, const void *)"
5d0641a4 70.Fc
984263bc 71.Ft int
5d0641a4
PA
72.Fo mergesort
73.Fa "void *base"
74.Fa "size_t nmemb"
75.Fa "size_t size"
25c75583 76.Fa "int (*compar)(const void *, const void *)"
5d0641a4 77.Fc
984263bc
MD
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 .
5d0641a4
PA
100The
101.Fn mergesort
102function
984263bc
MD
103behaves similarly, but
104.Em requires
105that
106.Fa size
107be greater than
108.Dq "sizeof(void *) / 2" .
109.Pp
110The contents of the array
111.Fa base
112are sorted in ascending order according to
113a comparison function pointed to by
114.Fa compar ,
115which requires two arguments pointing to the objects being
116compared.
117.Pp
118The comparison function must return an integer less than, equal to, or
119greater than zero if the first argument is considered to be respectively
120less than, equal to, or greater than the second.
121.Pp
5d0641a4
PA
122The
123.Fn qsort_r
124function behaves identically to
125.Fn qsort ,
126except that it takes an additional argument,
127.Fa thunk ,
128which is passed unchanged as the first argument to function pointed to
129.Fa compar .
130This allows the comparison function to access additional
131data without using global variables, and thus
132.Fn qsort_r
133is suitable for use in functions which must be reentrant.
134.Pp
135The algorithms implemented by
136.Fn qsort ,
137.Fn qsort_r ,
984263bc
MD
138and
139.Fn heapsort
140are
141.Em not
142stable, that is, if two members compare as equal, their order in
143the sorted array is undefined.
5d0641a4 144The
984263bc 145.Fn mergesort
5d0641a4 146algorithm is stable.
984263bc
MD
147.Pp
148The
149.Fn qsort
5d0641a4
PA
150and
151.Fn qsort_r
152functions are an implementation of C.A.R.
153Hoare's
154.Dq quicksort
155algorithm,
156a variant of partition-exchange sorting; in particular, see
157.An D.E. Knuth Ns 's
158.%T "Algorithm Q" .
159.Sy Quicksort
984263bc
MD
160takes O N lg N average time.
161This implementation uses median selection to avoid its
162O N**2 worst-case behavior.
163.Pp
164The
165.Fn heapsort
5d0641a4
PA
166function is an implementation of
167.An "J.W.J. William" Ns 's
168.Dq heapsort
169algorithm,
170a variant of selection sorting; in particular, see
171.An "D.E. Knuth" Ns 's
172.%T "Algorithm H" .
173.Sy Heapsort
984263bc
MD
174takes O N lg N worst-case time.
175Its
176.Em only
177advantage over
178.Fn qsort
179is that it uses almost no additional memory; while
180.Fn qsort
181does not allocate memory, it is implemented using recursion.
182.Pp
183The function
184.Fn mergesort
185requires additional memory of size
186.Fa nmemb *
187.Fa size
188bytes; it should be used only when space is not at a premium.
5d0641a4
PA
189The
190.Fn mergesort
191function
984263bc
MD
192is optimized for data with pre-existing order; its worst case
193time is O N lg N; its best case is O N.
194.Pp
195Normally,
196.Fn qsort
197is faster than
198.Fn mergesort
199is faster than
200.Fn heapsort .
201Memory availability and pre-existing order in the data can make this
202untrue.
203.Sh RETURN VALUES
204The
205.Fn qsort
5d0641a4
PA
206and
207.Fn qsort_r
208functions
209return no value.
984263bc
MD
210.Pp
211.Rv -std heapsort mergesort
0b84df5c
SW
212.Sh COMPATIBILITY
213Previous versions of
214.Fn qsort
215did not permit the comparison routine itself to call
216.Fn qsort 3 .
217This is no longer true.
984263bc
MD
218.Sh ERRORS
219The
220.Fn heapsort
221and
222.Fn mergesort
223functions succeed unless:
224.Bl -tag -width Er
225.It Bq Er EINVAL
226The
227.Fa size
228argument is zero, or,
229the
230.Fa size
231argument to
232.Fn mergesort
233is less than
234.Dq "sizeof(void *) / 2" .
235.It Bq Er ENOMEM
5d0641a4
PA
236The
237.Fn heapsort
984263bc
MD
238or
239.Fn mergesort
5d0641a4 240functions
984263bc
MD
241were unable to allocate memory.
242.El
984263bc
MD
243.Sh SEE ALSO
244.Xr sort 1 ,
245.Xr radixsort 3
246.Rs
247.%A Hoare, C.A.R.
248.%D 1962
249.%T "Quicksort"
250.%J "The Computer Journal"
251.%V 5:1
252.%P pp. 10-15
253.Re
254.Rs
255.%A Williams, J.W.J
256.%D 1964
257.%T "Heapsort"
258.%J "Communications of the ACM"
259.%V 7:1
260.%P pp. 347-348
261.Re
262.Rs
263.%A Knuth, D.E.
264.%D 1968
265.%B "The Art of Computer Programming"
266.%V Vol. 3
267.%T "Sorting and Searching"
268.%P pp. 114-123, 145-149
269.Re
270.Rs
5d0641a4 271.%A McIlroy, P.M.
984263bc
MD
272.%T "Optimistic Sorting and Information Theoretic Complexity"
273.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
274.%V January 1992
275.Re
276.Rs
277.%A Bentley, J.L.
5d0641a4 278.%A McIlroy, M.D.
984263bc 279.%T "Engineering a Sort Function"
5d0641a4
PA
280.%J "Software--Practice and Experience"
281.%V Vol. 23(11)
282.%P pp. 1249-1265
283.%D November\ 1993
984263bc
MD
284.Re
285.Sh STANDARDS
286The
287.Fn qsort
288function
289conforms to
290.St -isoC .