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