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 January 20, 2020
  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 .Fd #define __STDC_WANT_LIB_EXT1__ 1
 102 .Ft errno_t
 103 .Fo qsort_s
 104 .Fa "void *base"
 105 .Fa "rsize_t nmemb"
 106 .Fa "rsize_t size"
 107 .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *, void *\*[rp]"
 108 .Fa "void *thunk"
 109 .Fc
 110 .Sh DESCRIPTION
 111 The
 112 .Fn qsort
 113 function is a modified partition-exchange sort, or quicksort.
 114 The
 115 .Fn heapsort
 116 function is a modified selection sort.
 117 The
 118 .Fn mergesort
 119 function is a modified merge sort with exponential search
 120 intended for sorting data with pre-existing order.
 121 .Pp
 122 The
 123 .Fn qsort
 124 and
 125 .Fn heapsort
 126 functions sort an array of
 127 .Fa nmemb
 128 objects, the initial member of which is pointed to by
 129 .Fa base .
 130 The size of each object is specified by
 131 .Fa size .
 132 The
 133 .Fn mergesort
 134 function
 135 behaves similarly, but
 136 .Em requires
 137 that
 138 .Fa size
 139 be greater than
 140 .Dq "sizeof(void *) / 2" .
 141 .Pp
 142 The contents of the array
 143 .Fa base
 144 are sorted in ascending order according to
 145 a comparison function pointed to by
 146 .Fa compar ,
 147 which requires two arguments pointing to the objects being
 148 compared.
 149 .Pp
 150 The comparison function must return an integer less than, equal to, or
 151 greater than zero if the first argument is considered to be respectively
 152 less than, equal to, or greater than the second.
 153 .Pp
 154 The
 155 .Fn qsort_r
 156 function behaves identically to
 157 .Fn qsort ,
 158 except that it takes an additional argument,
 159 .Fa thunk ,
 160 which is passed unchanged as the first argument to function pointed to
 161 .Fa compar .
 162 This allows the comparison function to access additional
 163 data without using global variables, and thus
 164 .Fn qsort_r
 165 is suitable for use in functions which must be reentrant.
 166 The
 167 .Fn qsort_b
 168 function behaves identically to
 169 .Fn qsort ,
 170 except that it takes a block, rather than a function pointer.
 171 .Pp
 172 The algorithms implemented by
 173 .Fn qsort ,
 174 .Fn qsort_r ,
 175 and
 176 .Fn heapsort
 177 are
 178 .Em not
 179 stable, that is, if two members compare as equal, their order in
 180 the sorted array is undefined.
 181 The
 182 .Fn heapsort_b
 183 function behaves identically to
 184 .Fn heapsort ,
 185 except that it takes a block, rather than a function pointer.
 186 The
 187 .Fn mergesort
 188 algorithm is stable.
 189 The
 190 .Fn mergesort_b
 191 function behaves identically to
 192 .Fn mergesort ,
 193 except that it takes a block, rather than a function pointer.
 194 .Pp
 195 The
 196 .Fn qsort
 197 and
 198 .Fn qsort_r
 199 functions are an implementation of C.A.R.
 200 Hoare's
 201 .Dq quicksort
 202 algorithm,
 203 a variant of partition-exchange sorting; in particular, see
 204 .An D.E. Knuth Ns 's
 205 .%T "Algorithm Q" .
 206 .Sy Quicksort
 207 takes O N lg N average time.
 208 This implementation uses median selection to avoid its
 209 O N**2 worst-case behavior.
 210 .Pp
 211 The
 212 .Fn heapsort
 213 function is an implementation of
 214 .An "J.W.J. William" Ns 's
 215 .Dq heapsort
 216 algorithm,
 217 a variant of selection sorting; in particular, see
 218 .An "D.E. Knuth" Ns 's
 219 .%T "Algorithm H" .
 220 .Sy Heapsort
 221 takes O N lg N worst-case time.
 222 Its
 223 .Em only
 224 advantage over
 225 .Fn qsort
 226 is that it uses almost no additional memory; while
 227 .Fn qsort
 228 does not allocate memory, it is implemented using recursion.
 229 .Pp
 230 The function
 231 .Fn mergesort
 232 requires additional memory of size
 233 .Fa nmemb *
 234 .Fa size
 235 bytes; it should be used only when space is not at a premium.
 236 The
 237 .Fn mergesort
 238 function
 239 is optimized for data with pre-existing order; its worst case
 240 time is O N lg N; its best case is O N.
 241 .Pp
 242 Normally,
 243 .Fn qsort
 244 is faster than
 245 .Fn mergesort
 246 is faster than
 247 .Fn heapsort .
 248 Memory availability and pre-existing order in the data can make this
 249 untrue.
 250 .Pp
 251 The
 252 .Fn qsort_s
 253 function behaves the same as
 254 .Fn qsort_r , except that:
 255 .Bl -dash
 256 .It
 257 The order of arguments is different
 258 .It
 259 The order of arguments to
 260 .Fa compar
 261 is different
 262 .It
 263 if
 264 .Fa nmemb
 265 or
 266 .Fa size
 267 are greater than
 268 .Dv RSIZE_MAX ,
 269 or
 270 .Fa nmemb
 271 is not zero and
 272 .Fa compar
 273 is NULL, then the runtime-constraint handler is called, and
 274 .Fn qsort_s
 275 returns an error.
 276 Note that the handler is called before
 277 .Fn qsort_s
 278 returns the error, and the handler function might not return.
 279 .El
 280 .Sh RETURN VALUES
 281 The
 282 .Fn qsort
 283 and
 284 .Fn qsort_r
 285 functions
 286 return no value.
 287 The
 288 .Fn qsort_s
 289 function returns zero on success, non-zero on error.
 290 .Pp
 291 .Rv -std heapsort mergesort
 292 .Sh EXAMPLES
 293 A sample program that sorts an array of
 294 .Vt int
 295 values in place using
 296 .Fn qsort ,
 297 and then prints the sorted array to standard output is:
 298 .Bd -literal
 299 #include <stdio.h>
 300 #include <stdlib.h>
 301
 302 /*
 303  * Custom comparison function that compares 'int' values through pointers
 304  * passed by qsort(3).
 305  */
 306 static int
 307 int_compare(const void *p1, const void *p2)
 308 {
 309         int left = *(const int *)p1;
 310         int right = *(const int *)p2;
 311
 312         return ((left > right) - (left < right));
 313 }
 314
 315 /*
 316  * Sort an array of 'int' values and print it to standard output.
 317  */
 318 int
 319 main(void)
 320 {
 321         int int_array[] = { 4, 5, 9, 3, 0, 1, 7, 2, 8, 6 };
 322         size_t array_size = sizeof(int_array) / sizeof(int_array[0]);
 323         size_t k;
 324
 325         qsort(&int_array, array_size, sizeof(int_array[0]), int_compare);
 326         for (k = 0; k < array_size; k++)
 327                 printf(" %d", int_array[k]);
 328         puts("");
 329         return (EXIT_SUCCESS);
 330 }
 331 .Ed
 332 .Sh COMPATIBILITY
 333 The order of arguments for the comparison function used with
 334 .Fn qsort_r
 335 is different from the one used by
 336 .Fn qsort_s ,
 337 and the GNU libc implementation of
 338 .Fn qsort_r .
 339 When porting software written for GNU libc, it is usually possible
 340 to replace
 341 .Fn qsort_r
 342 with
 343 .Fn qsort_s
 344 to work around this problem.
 345 .Pp
 346 .Fn qsort_s
 347 is part of the
 348 .Em optional
 349 Annex K portion of
 350 .St -isoC-2011
 351 and may not be portable to other standards-conforming platforms.
 352 .Pp
 353 Previous versions of
 354 .Fn qsort
 355 did not permit the comparison routine itself to call
 356 .Fn qsort 3 .
 357 This is no longer true.
 358 .Sh ERRORS
 359 The
 360 .Fn heapsort
 361 and
 362 .Fn mergesort
 363 functions succeed unless:
 364 .Bl -tag -width Er
 365 .It Bq Er EINVAL
 366 The
 367 .Fa size
 368 argument is zero, or,
 369 the
 370 .Fa size
 371 argument to
 372 .Fn mergesort
 373 is less than
 374 .Dq "sizeof(void *) / 2" .
 375 .It Bq Er ENOMEM
 376 The
 377 .Fn heapsort
 378 or
 379 .Fn mergesort
 380 functions
 381 were unable to allocate memory.
 382 .El
 383 .Sh SEE ALSO
 384 .Xr sort 1 ,
 385 .Xr radixsort 3
 386 .Rs
 387 .%A Hoare, C.A.R.
 388 .%D 1962
 389 .%T "Quicksort"
 390 .%J "The Computer Journal"
 391 .%V 5:1
 392 .%P pp. 10-15
 393 .Re
 394 .Rs
 395 .%A Williams, J.W.J
 396 .%D 1964
 397 .%T "Heapsort"
 398 .%J "Communications of the ACM"
 399 .%V 7:1
 400 .%P pp. 347-348
 401 .Re
 402 .Rs
 403 .%A Knuth, D.E.
 404 .%D 1968
 405 .%B "The Art of Computer Programming"
 406 .%V Vol. 3
 407 .%T "Sorting and Searching"
 408 .%P pp. 114-123, 145-149
 409 .Re
 410 .Rs
 411 .%A McIlroy, P.M.
 412 .%T "Optimistic Sorting and Information Theoretic Complexity"
 413 .%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
 414 .%V January 1992
 415 .Re
 416 .Rs
 417 .%A Bentley, J.L.
 418 .%A McIlroy, M.D.
 419 .%T "Engineering a Sort Function"
 420 .%J "Software--Practice and Experience"
 421 .%V Vol. 23(11)
 422 .%P pp. 1249-1265
 423 .%D November\ 1993
 424 .Re
 425 .Sh STANDARDS
 426 The
 427 .Fn qsort
 428 function
 429 conforms to
 430 .St -isoC .
 431 .Fn qsort_s
 432 conforms to
 433 .St -isoC-2011
 434 K.3.6.3.2.
 435 .Sh HISTORY
 436 The variants of these functions that take blocks as arguments first appeared in
 437 Mac OS X.
 438 This implementation was created by David Chisnall.