[apple/libc.git] / stdlib / qsort.3

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