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
| 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
|
34.\"
35.Dd February 20, 2013
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 EXAMPLES
209A sample program that sorts an array of
210.Vt int
211values in place using
212.Fn qsort ,
213and then prints the sorted array to standard output is:
214.Bd -literal
215#include <stdio.h>
216#include <stdlib.h>
217
218/*
219 * Custom comparison function that can compare 'int' values through pointers
220 * passed by qsort(3).
221 */
222static int
223int_compare(const void *p1, const void *p2)
224{
225 int left = *(const int *)p1;
226 int right = *(const int *)p2;
227
228 return ((left > right) - (left < right));
229}
230
231/*
232 * Sort an array of 'int' values and print it to standard output.
233 */
234int
235main(void)
236{
237 int int_array[] = { 4, 5, 9, 3, 0, 1, 7, 2, 8, 6 };
238 const size_t array_size = sizeof(int_array) / sizeof(int_array[0]);
239 size_t k;
240
241 qsort(&int_array, array_size, sizeof(int_array[0]), int_compare);
242 for (k = 0; k < array_size; k++)
243 printf(" %d", int_array[k]);
244 puts("");
245 return (EXIT_SUCCESS);
246}
247.Ed
248.Sh COMPATIBILITY
249Previous versions of
250.Fn qsort
251did not permit the comparison routine itself to call
252.Fn qsort 3 .
253This is no longer true.
254.Sh ERRORS
255The
256.Fn heapsort
257and
258.Fn mergesort
259functions succeed unless:
260.Bl -tag -width Er
261.It Bq Er EINVAL
262The
263.Fa size
264argument is zero, or,
265the
266.Fa size
267argument to
268.Fn mergesort
269is less than
270.Dq "sizeof(void *) / 2" .
271.It Bq Er ENOMEM
272The
273.Fn heapsort
274or
275.Fn mergesort
276functions
277were unable to allocate memory.
278.El
279.Sh SEE ALSO
280.Xr sort 1 ,
281.Xr radixsort 3
282.Rs
283.%A Hoare, C.A.R.
284.%D 1962
285.%T "Quicksort"
286.%J "The Computer Journal"
287.%V 5:1
288.%P pp. 10-15
289.Re
290.Rs
291.%A Williams, J.W.J
292.%D 1964
293.%T "Heapsort"
294.%J "Communications of the ACM"
295.%V 7:1
296.%P pp. 347-348
297.Re
298.Rs
299.%A Knuth, D.E.
300.%D 1968
301.%B "The Art of Computer Programming"
302.%V Vol. 3
303.%T "Sorting and Searching"
304.%P pp. 114-123, 145-149
305.Re
306.Rs
307.%A McIlroy, P.M.
308.%T "Optimistic Sorting and Information Theoretic Complexity"
309.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
310.%V January 1992
311.Re
312.Rs
313.%A Bentley, J.L.
314.%A McIlroy, M.D.
315.%T "Engineering a Sort Function"
316.%J "Software--Practice and Experience"
317.%V Vol. 23(11)
318.%P pp. 1249-1265
319.%D November\ 1993
320.Re
321.Sh STANDARDS
322The
323.Fn qsort
324function
325conforms to
326.St -isoC .
| 34.\"
35.Dd February 20, 2013
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 EXAMPLES
209A sample program that sorts an array of
210.Vt int
211values in place using
212.Fn qsort ,
213and then prints the sorted array to standard output is:
214.Bd -literal
215#include <stdio.h>
216#include <stdlib.h>
217
218/*
219 * Custom comparison function that can compare 'int' values through pointers
220 * passed by qsort(3).
221 */
222static int
223int_compare(const void *p1, const void *p2)
224{
225 int left = *(const int *)p1;
226 int right = *(const int *)p2;
227
228 return ((left > right) - (left < right));
229}
230
231/*
232 * Sort an array of 'int' values and print it to standard output.
233 */
234int
235main(void)
236{
237 int int_array[] = { 4, 5, 9, 3, 0, 1, 7, 2, 8, 6 };
238 const size_t array_size = sizeof(int_array) / sizeof(int_array[0]);
239 size_t k;
240
241 qsort(&int_array, array_size, sizeof(int_array[0]), int_compare);
242 for (k = 0; k < array_size; k++)
243 printf(" %d", int_array[k]);
244 puts("");
245 return (EXIT_SUCCESS);
246}
247.Ed
248.Sh COMPATIBILITY
249Previous versions of
250.Fn qsort
251did not permit the comparison routine itself to call
252.Fn qsort 3 .
253This is no longer true.
254.Sh ERRORS
255The
256.Fn heapsort
257and
258.Fn mergesort
259functions succeed unless:
260.Bl -tag -width Er
261.It Bq Er EINVAL
262The
263.Fa size
264argument is zero, or,
265the
266.Fa size
267argument to
268.Fn mergesort
269is less than
270.Dq "sizeof(void *) / 2" .
271.It Bq Er ENOMEM
272The
273.Fn heapsort
274or
275.Fn mergesort
276functions
277were unable to allocate memory.
278.El
279.Sh SEE ALSO
280.Xr sort 1 ,
281.Xr radixsort 3
282.Rs
283.%A Hoare, C.A.R.
284.%D 1962
285.%T "Quicksort"
286.%J "The Computer Journal"
287.%V 5:1
288.%P pp. 10-15
289.Re
290.Rs
291.%A Williams, J.W.J
292.%D 1964
293.%T "Heapsort"
294.%J "Communications of the ACM"
295.%V 7:1
296.%P pp. 347-348
297.Re
298.Rs
299.%A Knuth, D.E.
300.%D 1968
301.%B "The Art of Computer Programming"
302.%V Vol. 3
303.%T "Sorting and Searching"
304.%P pp. 114-123, 145-149
305.Re
306.Rs
307.%A McIlroy, P.M.
308.%T "Optimistic Sorting and Information Theoretic Complexity"
309.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
310.%V January 1992
311.Re
312.Rs
313.%A Bentley, J.L.
314.%A McIlroy, M.D.
315.%T "Engineering a Sort Function"
316.%J "Software--Practice and Experience"
317.%V Vol. 23(11)
318.%P pp. 1249-1265
319.%D November\ 1993
320.Re
321.Sh STANDARDS
322The
323.Fn qsort
324function
325conforms to
326.St -isoC .
|