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