lib/libc/stdlib/qsort.3

   1 .\"     $NetBSD: qsort.3,v 1.13 2003/08/07 16:43:42 agc Exp $
   2 .\"
   3 .\" Copyright (c) 1990, 1991, 1993
   4 .\"     The Regents of the University of California.  All rights reserved.
   5 .\"
   6 .\" This code is derived from software contributed to Berkeley by
   7 .\" the American National Standards Committee X3, on Information
   8 .\" Processing Systems.
   9 .\"
  10 .\" Redistribution and use in source and binary forms, with or without
  11 .\" modification, are permitted provided that the following conditions
  12 .\" are met:
  13 .\" 1. Redistributions of source code must retain the above copyright
  14 .\"    notice, this list of conditions and the following disclaimer.
  15 .\" 2. Redistributions in binary form must reproduce the above copyright
  16 .\"    notice, this list of conditions and the following disclaimer in the
  17 .\"    documentation and/or other materials provided with the distribution.
  18 .\" 3. Neither the name of the University nor the names of its contributors
  19 .\"    may be used to endorse or promote products derived from this software
  20 .\"    without specific prior written permission.
  21 .\"
  22 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32 .\" SUCH DAMAGE.
  33 .\"
  34 .\"     from: @(#)qsort.3       8.1 (Berkeley) 6/4/93
  35 .\"
  36 .Dd June 4, 1993
  37 .Dt QSORT 3
  38 .Os
  39 .Sh NAME
  40 .Nm qsort ,
  41 .Nm heapsort ,
  42 .Nm mergesort
  43 .Nd sort functions
  44 .Sh LIBRARY
  45 .Lb libc
  46 .Sh SYNOPSIS
  47 .In stdlib.h
  48 .Ft void
  49 .Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
  50 .Ft int
  51 .Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
  52 .Ft int
  53 .Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
  54 .Sh DESCRIPTION
  55 The
  56 .Fn qsort
  57 function is a modified partition-exchange sort, or quicksort.
  58 The
  59 .Fn heapsort
  60 function is a modified selection sort.
  61 The
  62 .Fn mergesort
  63 function is a modified merge sort with exponential search
  64 intended for sorting data with pre-existing order.
  65 .Pp
  66 The
  67 .Fn qsort
  68 and
  69 .Fn heapsort
  70 functions sort an array of
  71 .Fa nmemb
  72 objects, the initial member of which is pointed to by
  73 .Fa base .
  74 The size of each object is specified by
  75 .Fa size .
  76 .Fn mergesort
  77 behaves similarly, but
  78 .Em requires
  79 that
  80 .Fa size
  81 be greater than
  82 .Dq "sizeof(void *) / 2" .
  83 .Pp
  84 The contents of the array
  85 .Fa base
  86 are sorted in ascending order according to
  87 a comparison function pointed to by
  88 .Fa compar ,
  89 which requires two arguments pointing to the objects being
  90 compared.
  91 .Pp
  92 The comparison function must return an integer less than, equal to, or
  93 greater than zero if the first argument is considered to be respectively
  94 less than, equal to, or greater than the second.
  95 .Pp
  96 The functions
  97 .Fn qsort
  98 and
  99 .Fn heapsort
 100 are
 101 .Em not
 102 stable, that is, if two members compare as equal, their order in
 103 the sorted array is undefined.
 104 The function
 105 .Fn mergesort
 106 is stable.
 107 .Pp
 108 The
 109 .Fn qsort
 110 function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm,
 111 a variant of partition-exchange sorting; in particular, see D.E. Knuth's
 112 Algorithm Q.
 113 .Fn qsort
 114 takes O N lg N average time.
 115 This implementation uses median selection to avoid its
 116 O N**2 worst-case behavior.
 117 .Pp
 118 The
 119 .Fn heapsort
 120 function is an implementation of J.W.J. William's ``heapsort'' algorithm,
 121 a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H.
 122 .Fn heapsort
 123 takes O N lg N worst-case time.
 124 Its
 125 .Em only
 126 advantage over
 127 .Fn qsort
 128 is that it uses almost no additional memory; while
 129 .Fn qsort
 130 does not allocate memory, it is implemented using recursion.
 131 .Pp
 132 The function
 133 .Fn mergesort
 134 requires additional memory of size
 135 .Fa nmemb *
 136 .Fa size
 137 bytes; it should be used only when space is not at a premium.
 138 .Fn mergesort
 139 is optimized for data with pre-existing order; its worst case
 140 time is O N lg N; its best case is O N.
 141 .Pp
 142 Normally,
 143 .Fn qsort
 144 is faster than
 145 .Fn mergesort
 146 is faster than
 147 .Fn heapsort .
 148 Memory availability and pre-existing order in the data can make this
 149 untrue.
 150 .Sh RETURN VALUES
 151 The
 152 .Fn qsort
 153 function
 154 returns no value.
 155 .Pp
 156 Upon successful completion,
 157 .Fn heapsort
 158 and
 159 .Fn mergesort
 160 return 0.
 161 Otherwise, they return \-1 and the global variable
 162 .Va errno
 163 is set to indicate the error.
 164 .Sh ERRORS
 165 The
 166 .Fn heapsort
 167 function succeeds 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 .
 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 .%D 1993
 221 .%T "Optimistic Sorting and Information Theoretic Complexity"
 222 .%J "Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
 223 .%P pp. 467-474
 224 .Re
 225 .Rs
 226 .%A Bentley, J.L. and McIlroy, M.D.
 227 .%D 1993
 228 .%T "Engineering a Sort Function"
 229 .%J "Software-Practice and Experience"
 230 .%V Vol. 23
 231 .%P pp. 1249-1265
 232 .Re
 233 .Sh STANDARDS
 234 The
 235 .Fn qsort
 236 function
 237 conforms to
 238 .St -ansiC .