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. All advertising materials mentioning features or use of this software
  17 .\"    must display the following acknowledgement:
  18 .\"     This product includes software developed by the University of
  19 .\"     California, Berkeley and its contributors.
  20 .\" 4. Neither the name of the University nor the names of its contributors
  21 .\"    may be used to endorse or promote products derived from this software
  22 .\"    without specific prior written permission.
  23 .\"
  24 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34 .\" SUCH DAMAGE.
  35 .\"
  36 .\"     @(#)qsort.3     8.1 (Berkeley) 6/4/93
  37 .\"
  38 .Dd June 4, 1993
  39 .Dt QSORT 3
  40 .Os
  41 .Sh NAME
  42 .Nm qsort, heapsort, mergesort
  43 .Nd sort functions
  44 .Sh SYNOPSIS
  45 .Fd #include <stdlib.h>
  46 .Ft void
  47 .Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
  48 .Ft int
  49 .Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
  50 .Ft int
  51 .Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
  52 .Sh DESCRIPTION
  53 The
  54 .Fn qsort
  55 function is a modified partition-exchange sort, or quicksort.
  56 The
  57 .Fn heapsort
  58 function is a modified selection sort.
  59 The
  60 .Fn mergesort
  61 function is a modified merge sort with exponential search
  62 intended for sorting data with pre-existing order.
  63 .Pp
  64 The
  65 .Fn qsort
  66 and
  67 .Fn heapsort
  68 functions sort an array of
  69 .Fa nmemb
  70 objects, the initial member of which is pointed to by
  71 .Fa base .
  72 The size of each object is specified by
  73 .Fa size .
  74 .Fn Mergesort
  75 behaves similarly, but
  76 .Em requires
  77 that
  78 .Fa size
  79 be greater than
  80 .Dq "sizeof(void *) / 2" .
  81 .Pp
  82 The contents of the array
  83 .Fa base
  84 are sorted in ascending order according to
  85 a comparison function pointed to by
  86 .Fa compar ,
  87 which requires two arguments pointing to the objects being
  88 compared.
  89 .Pp
  90 The comparison function must return an integer less than, equal to, or
  91 greater than zero if the first argument is considered to be respectively
  92 less than, equal to, or greater than the second.
  93 .Pp
  94 The functions
  95 .Fn qsort
  96 and
  97 .Fn heapsort
  98 are
  99 .Em not
 100 stable, that is, if two members compare as equal, their order in
 101 the sorted array is undefined.
 102 The function
 103 .Fn mergesort
 104 is stable.
 105 .Pp
 106 The
 107 .Fn qsort
 108 function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm,
 109 a variant of partition-exchange sorting; in particular, see D.E. Knuth's
 110 Algorithm Q.
 111 .Fn Qsort
 112 takes O N lg N average time.
 113 This implementation uses median selection to avoid its
 114 O N**2 worst-case behavior.
 115 .Pp
 116 The
 117 .Fn heapsort
 118 function is an implementation of J.W.J. William's ``heapsort'' algorithm,
 119 a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H.
 120 .Fn Heapsort
 121 takes O N lg N worst-case time.
 122 Its
 123 .Em only
 124 advantage over
 125 .Fn qsort
 126 is that it uses almost no additional memory; while
 127 .Fn qsort
 128 does not allocate memory, it is implemented using recursion.
 129 .Pp
 130 The function
 131 .Fn mergesort
 132 requires additional memory of size
 133 .Fa nmemb *
 134 .Fa size
 135 bytes; it should be used only when space is not at a premium.
 136 .Fn Mergesort
 137 is optimized for data with pre-existing order; its worst case
 138 time is O N lg N; its best case is O N.
 139 .Pp
 140 Normally,
 141 .Fn qsort
 142 is faster than
 143 .Fn mergesort
 144 is faster than
 145 .Fn heapsort .
 146 Memory availability and pre-existing order in the data can make this
 147 untrue.
 148 .Sh RETURN VALUES
 149 The
 150 .Fn qsort
 151 function
 152 returns no value.
 153 .Pp
 154 Upon successful completion,
 155 .Fn heapsort
 156 and
 157 .Fn mergesort
 158 return 0.
 159 Otherwise, they return \-1 and the global variable
 160 .Va errno
 161 is set to indicate the error.
 162 .Sh ERRORS
 163 The
 164 .Fn heapsort
 165 and
 166 .Fn mergesort
 167 functions succeed unless:
 168 .Bl -tag -width Er
 169 .It Bq Er EINVAL
 170 The
 171 .Fa size
 172 argument is zero, or,
 173 the
 174 .Fa size
 175 argument to
 176 .Fn mergesort
 177 is less than
 178 .Dq "sizeof(void *) / 2" .
 179 .It Bq Er ENOMEM
 180 .Fn Heapsort
 181 or
 182 .Fn mergesort
 183 were unable to allocate memory.
 184 .El
 185 .Sh COMPATIBILITY
 186 Previous versions of
 187 .Fn qsort
 188 did not permit the comparison routine itself to call
 189 .Fn qsort 3 .
 190 This is no longer true.
 191 .Sh SEE ALSO
 192 .Xr sort 1 ,
 193 .Xr radixsort 3
 194 .Rs
 195 .%A Hoare, C.A.R.
 196 .%D 1962
 197 .%T "Quicksort"
 198 .%J "The Computer Journal"
 199 .%V 5:1
 200 .%P pp. 10-15
 201 .Re
 202 .Rs
 203 .%A Williams, J.W.J
 204 .%D 1964
 205 .%T "Heapsort"
 206 .%J "Communications of the ACM"
 207 .%V 7:1
 208 .%P pp. 347-348
 209 .Re
 210 .Rs
 211 .%A Knuth, D.E.
 212 .%D 1968
 213 .%B "The Art of Computer Programming"
 214 .%V Vol. 3
 215 .%T "Sorting and Searching"
 216 .%P pp. 114-123, 145-149
 217 .Re
 218 .Rs
 219 .%A Mcilroy, P.M.
 220 .%T "Optimistic Sorting and Information Theoretic Complexity"
 221 .%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
 222 .%V January 1992
 223 .Re
 224 .Rs
 225 .%A Bentley, J.L.
 226 .%T "Engineering a Sort Function"
 227 .%J "bentley@research.att.com"
 228 .%V January 1992
 229 .Re
 230 .Sh STANDARDS
 231 The
 232 .Fn qsort
 233 function
 234 conforms to
 235 .St -ansiC .