xref: /dragonfly/lib/libc/stdlib/qsort.3 (revision c03f08f3) 
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: src/lib/libc/stdlib/qsort.3,v 1.4.2.5 2001/12/14 18:33:58 ru Exp $
38.\" $DragonFly: src/lib/libc/stdlib/qsort.3,v 1.4 2006/02/17 19:35:06 swildner Exp $
39.\"
40.Dd June 4, 1993
41.Dt QSORT 3
42.Os
43.Sh NAME
44.Nm qsort ,
45.Nm heapsort ,
46.Nm mergesort
47.Nd sort functions
48.Sh LIBRARY
49.Lb libc
50.Sh SYNOPSIS
51.In stdlib.h
52.Ft void
53.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
54.Ft int
55.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
56.Ft int
57.Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
58.Sh DESCRIPTION
59The
60.Fn qsort
61function is a modified partition-exchange sort, or quicksort.
62The
63.Fn heapsort
64function is a modified selection sort.
65The
66.Fn mergesort
67function is a modified merge sort with exponential search
68intended for sorting data with pre-existing order.
69.Pp
70The
71.Fn qsort
72and
73.Fn heapsort
74functions sort an array of
75.Fa nmemb
76objects, the initial member of which is pointed to by
77.Fa base .
78The size of each object is specified by
79.Fa size .
80.Fn Mergesort
81behaves similarly, but
82.Em requires
83that
84.Fa size
85be greater than
86.Dq "sizeof(void *) / 2" .
87.Pp
88The contents of the array
89.Fa base
90are sorted in ascending order according to
91a comparison function pointed to by
92.Fa compar ,
93which requires two arguments pointing to the objects being
94compared.
95.Pp
96The comparison function must return an integer less than, equal to, or
97greater than zero if the first argument is considered to be respectively
98less than, equal to, or greater than the second.
99.Pp
100The functions
101.Fn qsort
102and
103.Fn heapsort
104are
105.Em not
106stable, that is, if two members compare as equal, their order in
107the sorted array is undefined.
108The function
109.Fn mergesort
110is stable.
111.Pp
112The
113.Fn qsort
114function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm,
115a variant of partition-exchange sorting; in particular, see D.E. Knuth's
116Algorithm Q.
117.Fn Qsort
118takes O N lg N average time.
119This implementation uses median selection to avoid its
120O N**2 worst-case behavior.
121.Pp
122The
123.Fn heapsort
124function is an implementation of J.W.J. William's ``heapsort'' algorithm,
125a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H.
126.Fn Heapsort
127takes O N lg N worst-case time.
128Its
129.Em only
130advantage over
131.Fn qsort
132is that it uses almost no additional memory; while
133.Fn qsort
134does not allocate memory, it is implemented using recursion.
135.Pp
136The function
137.Fn mergesort
138requires additional memory of size
139.Fa nmemb *
140.Fa size
141bytes; it should be used only when space is not at a premium.
142.Fn Mergesort
143is optimized for data with pre-existing order; its worst case
144time is O N lg N; its best case is O N.
145.Pp
146Normally,
147.Fn qsort
148is faster than
149.Fn mergesort
150is faster than
151.Fn heapsort .
152Memory availability and pre-existing order in the data can make this
153untrue.
154.Sh RETURN VALUES
155The
156.Fn qsort
157function
158returns no value.
159.Pp
160.Rv -std heapsort mergesort
161.Sh COMPATIBILITY
162Previous versions of
163.Fn qsort
164did not permit the comparison routine itself to call
165.Fn qsort 3 .
166This is no longer true.
167.Sh ERRORS
168The
169.Fn heapsort
170and
171.Fn mergesort
172functions succeed unless:
173.Bl -tag -width Er
174.It Bq Er EINVAL
175The
176.Fa size
177argument is zero, or,
178the
179.Fa size
180argument to
181.Fn mergesort
182is less than
183.Dq "sizeof(void *) / 2" .
184.It Bq Er ENOMEM
185.Fn Heapsort
186or
187.Fn mergesort
188were unable to allocate memory.
189.El
190.Sh SEE ALSO
191.Xr sort 1 ,
192.Xr radixsort 3
193.Rs
194.%A Hoare, C.A.R.
195.%D 1962
196.%T "Quicksort"
197.%J "The Computer Journal"
198.%V 5:1
199.%P pp. 10-15
200.Re
201.Rs
202.%A Williams, J.W.J
203.%D 1964
204.%T "Heapsort"
205.%J "Communications of the ACM"
206.%V 7:1
207.%P pp. 347-348
208.Re
209.Rs
210.%A Knuth, D.E.
211.%D 1968
212.%B "The Art of Computer Programming"
213.%V Vol. 3
214.%T "Sorting and Searching"
215.%P pp. 114-123, 145-149
216.Re
217.Rs
218.%A Mcilroy, P.M.
219.%T "Optimistic Sorting and Information Theoretic Complexity"
220.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
221.%V January 1992
222.Re
223.Rs
224.%A Bentley, J.L.
225.%T "Engineering a Sort Function"
226.%J "bentley@research.att.com"
227.%V January 1992
228.Re
229.Sh STANDARDS
230The
231.Fn qsort
232function
233conforms to
234.St -isoC .
235