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 April 19, 2023
  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 "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *, void *\*[rp]"
  71 .Fa "void *thunk"
  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 last 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
 274 .Dv NULL
 275 or
 276 .Fa size
 277 is zero, then the runtime-constraint handler is called, and
 278 .Fn qsort_s
 279 returns an error.
 280 Note that the handler is called before
 281 .Fn qsort_s
 282 returns the error, and the handler function might not return.
 283 .El
 284 .Sh RETURN VALUES
 285 The
 286 .Fn qsort
 287 and
 288 .Fn qsort_r
 289 functions
 290 return no value.
 291 The
 292 .Fn qsort_s
 293 function returns zero on success, non-zero on error.
 294 .Pp
 295 .Rv -std heapsort mergesort
 296 .Sh EXAMPLES
 297 A sample program that sorts an array of
 298 .Vt int
 299 values in place using
 300 .Fn qsort ,
 301 and then prints the sorted array to standard output is:
 302 .Bd -literal
 303 #include <stdio.h>
 304 #include <stdlib.h>
 305
 306 /*
 307  * Custom comparison function that compares 'int' values through pointers
 308  * passed by qsort(3).
 309  */
 310 static int
 311 int_compare(const void *p1, const void *p2)
 312 {
 313         int left = *(const int *)p1;
 314         int right = *(const int *)p2;
 315
 316         return ((left > right) - (left < right));
 317 }
 318
 319 /*
 320  * Sort an array of 'int' values and print it to standard output.
 321  */
 322 int
 323 main(void)
 324 {
 325         int int_array[] = { 4, 5, 9, 3, 0, 1, 7, 2, 8, 6 };
 326         size_t array_size = sizeof(int_array) / sizeof(int_array[0]);
 327         size_t k;
 328
 329         qsort(&int_array, array_size, sizeof(int_array[0]), int_compare);
 330         for (k = 0; k < array_size; k++)
 331                 printf(" %d", int_array[k]);
 332         puts("");
 333         return (EXIT_SUCCESS);
 334 }
 335 .Ed
 336 .Sh COMPATIBILITY
 337 The order of arguments for the comparison function used with
 338 .Fn qsort_r
 339 is different from the one used by
 340 .Fn qsort_s ,
 341 and the GNU libc implementation of
 342 .Fn qsort_r .
 343 When porting software written for GNU libc, it is usually possible
 344 to replace
 345 .Fn qsort_r
 346 with
 347 .Fn qsort_s
 348 to work around this problem.
 349 .Pp
 350 .Fn qsort_s
 351 is part of the
 352 .Em optional
 353 Annex K portion of
 354 .St -isoC-2011
 355 and may not be portable to other standards-conforming platforms.
 356 .Pp
 357 Previous versions of
 358 .Fn qsort
 359 did not permit the comparison routine itself to call
 360 .Fn qsort 3 .
 361 This is no longer true.
 362 .Sh ERRORS
 363 The
 364 .Fn heapsort
 365 and
 366 .Fn mergesort
 367 functions succeed unless:
 368 .Bl -tag -width Er
 369 .It Bq Er EINVAL
 370 The
 371 .Fa size
 372 argument is zero, or,
 373 the
 374 .Fa size
 375 argument to
 376 .Fn mergesort
 377 is less than
 378 .Dq "sizeof(void *) / 2" .
 379 .It Bq Er ENOMEM
 380 The
 381 .Fn heapsort
 382 or
 383 .Fn mergesort
 384 functions
 385 were unable to allocate memory.
 386 .El
 387 .Sh SEE ALSO
 388 .Xr sort 1 ,
 389 .Xr radixsort 3
 390 .Rs
 391 .%A Hoare, C.A.R.
 392 .%D 1962
 393 .%T "Quicksort"
 394 .%J "The Computer Journal"
 395 .%V 5:1
 396 .%P pp. 10-15
 397 .Re
 398 .Rs
 399 .%A Williams, J.W.J
 400 .%D 1964
 401 .%T "Heapsort"
 402 .%J "Communications of the ACM"
 403 .%V 7:1
 404 .%P pp. 347-348
 405 .Re
 406 .Rs
 407 .%A Knuth, D.E.
 408 .%D 1968
 409 .%B "The Art of Computer Programming"
 410 .%V Vol. 3
 411 .%T "Sorting and Searching"
 412 .%P pp. 114-123, 145-149
 413 .Re
 414 .Rs
 415 .%A McIlroy, P.M.
 416 .%T "Optimistic Sorting and Information Theoretic Complexity"
 417 .%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
 418 .%V January 1992
 419 .Re
 420 .Rs
 421 .%A Bentley, J.L.
 422 .%A McIlroy, M.D.
 423 .%T "Engineering a Sort Function"
 424 .%J "Software--Practice and Experience"
 425 .%V Vol. 23(11)
 426 .%P pp. 1249-1265
 427 .%D November\ 1993
 428 .Re
 429 .Sh STANDARDS
 430 The
 431 .Fn qsort
 432 function
 433 conforms to
 434 .St -isoC .
 435 .Fn qsort_s
 436 conforms to
 437 .St -isoC-2011
 438 K.3.6.3.2.
 439 .Sh HISTORY
 440 The variants of these functions that take blocks as arguments first appeared in
 441 Mac OS X.
 442 This implementation was created by David Chisnall.
 443 .Pp
 444 In
 445 .Fx 14.0 ,
 446 the prototype of
 447 .Fn qsort_r
 448 was updated to match POSIX.