1 .\" Copyright (c) 1990, 1991, 1993
2 .\" The Regents of the University of California. All rights reserved.
4 .\" This code is derived from software contributed to Berkeley by
5 .\" the American National Standards Committee X3, on Information
6 .\" Processing Systems.
8 .\" Redistribution and use in source and binary forms, with or without
9 .\" modification, are permitted provided that the following conditions
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. 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.
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
32 .\" @(#)qsort.3 8.1 (Berkeley) 6/4/93
39 .Nm qsort , qsort_b , qsort_r , heapsort , heapsort_b , mergesort, mergesort_b
50 .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
57 .Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]"
65 .Fa "int \*[lp]*compar\*[rp]\*[lp]void *, const void *, const void *\*[rp]"
72 .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
79 .Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]"
86 .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
93 .Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]"
98 function is a modified partition-exchange sort, or quicksort.
101 function is a modified selection sort.
104 function is a modified merge sort with exponential search
105 intended for sorting data with pre-existing order.
111 functions sort an array of
113 objects, the initial member of which is pointed to by
115 The size of each object is specified by
120 behaves similarly, but
125 .Dq "sizeof(void *) / 2" .
127 The contents of the array
129 are sorted in ascending order according to
130 a comparison function pointed to by
132 which requires two arguments pointing to the objects being
135 The comparison function must return an integer less than, equal to, or
136 greater than zero if the first argument is considered to be respectively
137 less than, equal to, or greater than the second.
141 function behaves identically to
143 except that it takes an additional argument,
145 which is passed unchanged as the first argument to function pointed to
147 This allows the comparison function to access additional
148 data without using global variables, and thus
150 is suitable for use in functions which must be reentrant.
153 function behaves identically to
155 except that it takes a block, rather than a function pointer.
157 The algorithms implemented by
164 stable, that is, if two members compare as equal, their order in
165 the sorted array is undefined.
168 function behaves identically to
170 except that it takes a block, rather than a function pointer.
176 function behaves identically to
178 except that it takes a block, rather than a function pointer.
184 functions are an implementation of C.A.R.
188 a variant of partition-exchange sorting; in particular, see
192 takes O N lg N average time.
193 This implementation uses median selection to avoid its
194 O N**2 worst-case behavior.
198 function is an implementation of
199 .An "J.W.J. William" Ns 's
202 a variant of selection sorting; in particular, see
203 .An "D.E. Knuth" Ns 's
206 takes O N lg N worst-case time.
211 is that it uses almost no additional memory; while
213 does not allocate memory, it is implemented using recursion.
217 requires additional memory of size
220 bytes; it should be used only when space is not at a premium.
224 is optimized for data with pre-existing order; its worst case
225 time is O N lg N; its best case is O N.
233 Memory availability and pre-existing order in the data can make this
243 .Rv -std heapsort mergesort
245 A sample program that sorts an array of
247 values in place using
249 and then prints the sorted array to standard output is:
255 * Custom comparison function that compares 'int' values through pointers
256 * passed by qsort(3).
259 int_compare(const void *p1, const void *p2)
261 int left = *(const int *)p1;
262 int right = *(const int *)p2;
264 return ((left > right) - (left < right));
268 * Sort an array of 'int' values and print it to standard output.
273 int int_array[] = { 4, 5, 9, 3, 0, 1, 7, 2, 8, 6 };
274 size_t array_size = sizeof(int_array) / sizeof(int_array[0]);
277 qsort(&int_array, array_size, sizeof(int_array[0]), int_compare);
278 for (k = 0; k < array_size; k++)
279 printf(" %d", int_array[k]);
281 return (EXIT_SUCCESS);
287 did not permit the comparison routine itself to call
289 This is no longer true.
295 functions succeed unless:
300 argument is zero, or,
306 .Dq "sizeof(void *) / 2" .
313 were unable to allocate memory.
322 .%J "The Computer Journal"
330 .%J "Communications of the ACM"
337 .%B "The Art of Computer Programming"
339 .%T "Sorting and Searching"
340 .%P pp. 114-123, 145-149
344 .%T "Optimistic Sorting and Information Theoretic Complexity"
345 .%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
351 .%T "Engineering a Sort Function"
352 .%J "Software--Practice and Experience"
364 The variants of these functions that take blocks as arguments first appeared in
366 This implementation was created by David Chisnall.