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