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 ,
  40 .Nm qsort_b ,
  41 .Nm qsort_r ,
  42 .Nm heapsort ,
  43 .Nm heapsort_b ,
  44 .Nm mergesort ,
  45 .Nm mergesort_b
  46 .Nd sort functions
  47 .Sh LIBRARY
  48 .Lb libc
  49 .Sh SYNOPSIS
  50 .In stdlib.h
  51 .Ft void
  52 .Fo qsort
  53 .Fa "void *base"
  54 .Fa "size_t nmemb"
  55 .Fa "size_t size"
  56 .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
  57 .Fc
  58 .Ft void
  59 .Fo qsort_b
  60 .Fa "void *base"
  61 .Fa "size_t nmemb"
  62 .Fa "size_t size"
  63 .Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]"
  64 .Fc
  65 .Ft void
  66 .Fo qsort_r
  67 .Fa "void *base"
  68 .Fa "size_t nmemb"
  69 .Fa "size_t size"
  70 .Fa "void *thunk"
  71 .Fa "int \*[lp]*compar\*[rp]\*[lp]void *, const void *, const void *\*[rp]"
  72 .Fc
  73 .Ft int
  74 .Fo heapsort
  75 .Fa "void *base"
  76 .Fa "size_t nmemb"
  77 .Fa "size_t size"
  78 .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
  79 .Fc
  80 .Ft int
  81 .Fo heapsort_b
  82 .Fa "void *base"
  83 .Fa "size_t nmemb"
  84 .Fa "size_t size"
  85 .Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]"
  86 .Fc
  87 .Ft int
  88 .Fo mergesort
  89 .Fa "void *base"
  90 .Fa "size_t nmemb"
  91 .Fa "size_t size"
  92 .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
  93 .Fc
  94 .Ft int
  95 .Fo mergesort_b
  96 .Fa "void *base"
  97 .Fa "size_t nmemb"
  98 .Fa "size_t size"
  99 .Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]"
 100 .Fc
 101 .Sh DESCRIPTION
 102 The
 103 .Fn qsort
 104 function is a modified partition-exchange sort, or quicksort.
 105 The
 106 .Fn heapsort
 107 function is a modified selection sort.
 108 The
 109 .Fn mergesort
 110 function is a modified merge sort with exponential search
 111 intended for sorting data with pre-existing order.
 112 .Pp
 113 The
 114 .Fn qsort
 115 and
 116 .Fn heapsort
 117 functions sort an array of
 118 .Fa nmemb
 119 objects, the initial member of which is pointed to by
 120 .Fa base .
 121 The size of each object is specified by
 122 .Fa size .
 123 The
 124 .Fn mergesort
 125 function
 126 behaves similarly, but
 127 .Em requires
 128 that
 129 .Fa size
 130 be greater than
 131 .Dq "sizeof(void *) / 2" .
 132 .Pp
 133 The contents of the array
 134 .Fa base
 135 are sorted in ascending order according to
 136 a comparison function pointed to by
 137 .Fa compar ,
 138 which requires two arguments pointing to the objects being
 139 compared.
 140 .Pp
 141 The comparison function must return an integer less than, equal to, or
 142 greater than zero if the first argument is considered to be respectively
 143 less than, equal to, or greater than the second.
 144 .Pp
 145 The
 146 .Fn qsort_r
 147 function behaves identically to
 148 .Fn qsort ,
 149 except that it takes an additional argument,
 150 .Fa thunk ,
 151 which is passed unchanged as the first argument to function pointed to
 152 .Fa compar .
 153 This allows the comparison function to access additional
 154 data without using global variables, and thus
 155 .Fn qsort_r
 156 is suitable for use in functions which must be reentrant.
 157 The
 158 .Fn qsort_b
 159 function behaves identically to
 160 .Fn qsort ,
 161 except that it takes a block, rather than a function pointer.
 162 .Pp
 163 The algorithms implemented by
 164 .Fn qsort ,
 165 .Fn qsort_r ,
 166 and
 167 .Fn heapsort
 168 are
 169 .Em not
 170 stable, that is, if two members compare as equal, their order in
 171 the sorted array is undefined.
 172 The
 173 .Fn heapsort_b
 174 function behaves identically to
 175 .Fn heapsort ,
 176 except that it takes a block, rather than a function pointer.
 177 The
 178 .Fn mergesort
 179 algorithm is stable.
 180 The
 181 .Fn mergesort_b
 182 function behaves identically to
 183 .Fn mergesort ,
 184 except that it takes a block, rather than a function pointer.
 185 .Pp
 186 The
 187 .Fn qsort
 188 and
 189 .Fn qsort_r
 190 functions are an implementation of C.A.R.
 191 Hoare's
 192 .Dq quicksort
 193 algorithm,
 194 a variant of partition-exchange sorting; in particular, see
 195 .An D.E. Knuth Ns 's
 196 .%T "Algorithm Q" .
 197 .Sy Quicksort
 198 takes O N lg N average time.
 199 This implementation uses median selection to avoid its
 200 O N**2 worst-case behavior.
 201 .Pp
 202 The
 203 .Fn heapsort
 204 function is an implementation of
 205 .An "J.W.J. William" Ns 's
 206 .Dq heapsort
 207 algorithm,
 208 a variant of selection sorting; in particular, see
 209 .An "D.E. Knuth" Ns 's
 210 .%T "Algorithm H" .
 211 .Sy Heapsort
 212 takes O N lg N worst-case time.
 213 Its
 214 .Em only
 215 advantage over
 216 .Fn qsort
 217 is that it uses almost no additional memory; while
 218 .Fn qsort
 219 does not allocate memory, it is implemented using recursion.
 220 .Pp
 221 The function
 222 .Fn mergesort
 223 requires additional memory of size
 224 .Fa nmemb *
 225 .Fa size
 226 bytes; it should be used only when space is not at a premium.
 227 The
 228 .Fn mergesort
 229 function
 230 is optimized for data with pre-existing order; its worst case
 231 time is O N lg N; its best case is O N.
 232 .Pp
 233 Normally,
 234 .Fn qsort
 235 is faster than
 236 .Fn mergesort
 237 is faster than
 238 .Fn heapsort .
 239 Memory availability and pre-existing order in the data can make this
 240 untrue.
 241 .Sh RETURN VALUES
 242 The
 243 .Fn qsort
 244 and
 245 .Fn qsort_r
 246 functions
 247 return no value.
 248 .Pp
 249 .Rv -std heapsort mergesort
 250 .Sh EXAMPLES
 251 A sample program that sorts an array of
 252 .Vt int
 253 values in place using
 254 .Fn qsort ,
 255 and then prints the sorted array to standard output is:
 256 .Bd -literal
 257 #include <stdio.h>
 258 #include <stdlib.h>
 259
 260 /*
 261  * Custom comparison function that compares 'int' values through pointers
 262  * passed by qsort(3).
 263  */
 264 static int
 265 int_compare(const void *p1, const void *p2)
 266 {
 267         int left = *(const int *)p1;
 268         int right = *(const int *)p2;
 269
 270         return ((left > right) - (left < right));
 271 }
 272
 273 /*
 274  * Sort an array of 'int' values and print it to standard output.
 275  */
 276 int
 277 main(void)
 278 {
 279         int int_array[] = { 4, 5, 9, 3, 0, 1, 7, 2, 8, 6 };
 280         size_t array_size = sizeof(int_array) / sizeof(int_array[0]);
 281         size_t k;
 282
 283         qsort(&int_array, array_size, sizeof(int_array[0]), int_compare);
 284         for (k = 0; k < array_size; k++)
 285                 printf(" %d", int_array[k]);
 286         puts("");
 287         return (EXIT_SUCCESS);
 288 }
 289 .Ed
 290 .Sh COMPATIBILITY
 291 Previous versions of
 292 .Fn qsort
 293 did not permit the comparison routine itself to call
 294 .Fn qsort 3 .
 295 This is no longer true.
 296 .Sh ERRORS
 297 The
 298 .Fn heapsort
 299 and
 300 .Fn mergesort
 301 functions succeed unless:
 302 .Bl -tag -width Er
 303 .It Bq Er EINVAL
 304 The
 305 .Fa size
 306 argument is zero, or,
 307 the
 308 .Fa size
 309 argument to
 310 .Fn mergesort
 311 is less than
 312 .Dq "sizeof(void *) / 2" .
 313 .It Bq Er ENOMEM
 314 The
 315 .Fn heapsort
 316 or
 317 .Fn mergesort
 318 functions
 319 were unable to allocate memory.
 320 .El
 321 .Sh SEE ALSO
 322 .Xr sort 1 ,
 323 .Xr radixsort 3
 324 .Rs
 325 .%A Hoare, C.A.R.
 326 .%D 1962
 327 .%T "Quicksort"
 328 .%J "The Computer Journal"
 329 .%V 5:1
 330 .%P pp. 10-15
 331 .Re
 332 .Rs
 333 .%A Williams, J.W.J
 334 .%D 1964
 335 .%T "Heapsort"
 336 .%J "Communications of the ACM"
 337 .%V 7:1
 338 .%P pp. 347-348
 339 .Re
 340 .Rs
 341 .%A Knuth, D.E.
 342 .%D 1968
 343 .%B "The Art of Computer Programming"
 344 .%V Vol. 3
 345 .%T "Sorting and Searching"
 346 .%P pp. 114-123, 145-149
 347 .Re
 348 .Rs
 349 .%A McIlroy, P.M.
 350 .%T "Optimistic Sorting and Information Theoretic Complexity"
 351 .%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
 352 .%V January 1992
 353 .Re
 354 .Rs
 355 .%A Bentley, J.L.
 356 .%A McIlroy, M.D.
 357 .%T "Engineering a Sort Function"
 358 .%J "Software--Practice and Experience"
 359 .%V Vol. 23(11)
 360 .%P pp. 1249-1265
 361 .%D November\ 1993
 362 .Re
 363 .Sh STANDARDS
 364 The
 365 .Fn qsort
 366 function
 367 conforms to
 368 .St -isoC .
 369 .Sh HISTORY
 370 The variants of these functions that take blocks as arguments first appeared in
 371 Mac OS X.
 372 This implementation was created by David Chisnall.