lib/libc/stdlib/qsort.3

   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. 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.
  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
  33 .\" $FreeBSD$
  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
  75 The
  76 .Fn qsort
  77 function is a modified partition-exchange sort, or quicksort.
  78 The
  79 .Fn heapsort
  80 function is a modified selection sort.
  81 The
  82 .Fn mergesort
  83 function is a modified merge sort with exponential search
  84 intended for sorting data with pre-existing order.
  85 .Pp
  86 The
  87 .Fn qsort
  88 and
  89 .Fn heapsort
  90 functions sort an array of
  91 .Fa nmemb
  92 objects, the initial member of which is pointed to by
  93 .Fa base .
  94 The size of each object is specified by
  95 .Fa size .
  96 The
  97 .Fn mergesort
  98 function
  99 behaves similarly, but
 100 .Em requires
 101 that
 102 .Fa size
 103 be greater than
 104 .Dq "sizeof(void *) / 2" .
 105 .Pp
 106 The contents of the array
 107 .Fa base
 108 are sorted in ascending order according to
 109 a comparison function pointed to by
 110 .Fa compar ,
 111 which requires two arguments pointing to the objects being
 112 compared.
 113 .Pp
 114 The comparison function must return an integer less than, equal to, or
 115 greater than zero if the first argument is considered to be respectively
 116 less than, equal to, or greater than the second.
 117 .Pp
 118 The
 119 .Fn qsort_r
 120 function behaves identically to
 121 .Fn qsort ,
 122 except that it takes an additional argument,
 123 .Fa thunk ,
 124 which is passed unchanged as the first argument to function pointed to
 125 .Fa compar .
 126 This allows the comparison function to access additional
 127 data without using global variables, and thus
 128 .Fn qsort_r
 129 is suitable for use in functions which must be reentrant.
 130 .Pp
 131 The algorithms implemented by
 132 .Fn qsort ,
 133 .Fn qsort_r ,
 134 and
 135 .Fn heapsort
 136 are
 137 .Em not
 138 stable, that is, if two members compare as equal, their order in
 139 the sorted array is undefined.
 140 The
 141 .Fn mergesort
 142 algorithm is stable.
 143 .Pp
 144 The
 145 .Fn qsort
 146 and
 147 .Fn qsort_r
 148 functions are an implementation of C.A.R.
 149 Hoare's
 150 .Dq quicksort
 151 algorithm,
 152 a variant of partition-exchange sorting; in particular, see
 153 .An D.E. Knuth Ns 's
 154 .%T "Algorithm Q" .
 155 .Sy Quicksort
 156 takes O N lg N average time.
 157 This implementation uses median selection to avoid its
 158 O N**2 worst-case behavior.
 159 .Pp
 160 The
 161 .Fn heapsort
 162 function is an implementation of
 163 .An "J.W.J. William" Ns 's
 164 .Dq heapsort
 165 algorithm,
 166 a variant of selection sorting; in particular, see
 167 .An "D.E. Knuth" Ns 's
 168 .%T "Algorithm H" .
 169 .Sy Heapsort
 170 takes O N lg N worst-case time.
 171 Its
 172 .Em only
 173 advantage over
 174 .Fn qsort
 175 is that it uses almost no additional memory; while
 176 .Fn qsort
 177 does not allocate memory, it is implemented using recursion.
 178 .Pp
 179 The function
 180 .Fn mergesort
 181 requires additional memory of size
 182 .Fa nmemb *
 183 .Fa size
 184 bytes; it should be used only when space is not at a premium.
 185 The
 186 .Fn mergesort
 187 function
 188 is optimized for data with pre-existing order; its worst case
 189 time is O N lg N; its best case is O N.
 190 .Pp
 191 Normally,
 192 .Fn qsort
 193 is faster than
 194 .Fn mergesort
 195 is faster than
 196 .Fn heapsort .
 197 Memory availability and pre-existing order in the data can make this
 198 untrue.
 199 .Sh RETURN VALUES
 200 The
 201 .Fn qsort
 202 and
 203 .Fn qsort_r
 204 functions
 205 return no value.
 206 .Pp
 207 .Rv -std heapsort mergesort
 208 .Sh EXAMPLES
 209 A sample program that sorts an array of
 210 .Vt int
 211 values in place using
 212 .Fn qsort ,
 213 and 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  */
 222 static int
 223 int_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  */
 234 int
 235 main(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
 249 Previous versions of
 250 .Fn qsort
 251 did not permit the comparison routine itself to call
 252 .Fn qsort 3 .
 253 This is no longer true.
 254 .Sh ERRORS
 255 The
 256 .Fn heapsort
 257 and
 258 .Fn mergesort
 259 functions succeed unless:
 260 .Bl -tag -width Er
 261 .It Bq Er EINVAL
 262 The
 263 .Fa size
 264 argument is zero, or,
 265 the
 266 .Fa size
 267 argument to
 268 .Fn mergesort
 269 is less than
 270 .Dq "sizeof(void *) / 2" .
 271 .It Bq Er ENOMEM
 272 The
 273 .Fn heapsort
 274 or
 275 .Fn mergesort
 276 functions
 277 were 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
 322 The
 323 .Fn qsort
 324 function
 325 conforms to
 326 .St -isoC .