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 .\" $FreeBSD: src/lib/libc/stdlib/qsort.3,v 1.4.2.5 2001/12/14 18:33:58 ru Exp $
  38 .\"
  39 .Dd June 4, 1993
  40 .Dt QSORT 3
  41 .Os
  42 .Sh NAME
  43 .Nm qsort , heapsort , mergesort
  44 .Nd sort functions
  45 .Sh LIBRARY
  46 .Lb libc
  47 .Sh SYNOPSIS
  48 .In stdlib.h
  49 .Ft void
  50 .Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
  51 .Ft int
  52 .Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
  53 .Ft int
  54 .Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
  55 .Sh DESCRIPTION
  56 The
  57 .Fn qsort
  58 function is a modified partition-exchange sort, or quicksort.
  59 The
  60 .Fn heapsort
  61 function is a modified selection sort.
  62 The
  63 .Fn mergesort
  64 function is a modified merge sort with exponential search
  65 intended for sorting data with pre-existing order.
  66 .Pp
  67 The
  68 .Fn qsort
  69 and
  70 .Fn heapsort
  71 functions sort an array of
  72 .Fa nmemb
  73 objects, the initial member of which is pointed to by
  74 .Fa base .
  75 The size of each object is specified by
  76 .Fa size .
  77 .Fn Mergesort
  78 behaves similarly, but
  79 .Em requires
  80 that
  81 .Fa size
  82 be greater than
  83 .Dq "sizeof(void *) / 2" .
  84 .Pp
  85 The contents of the array
  86 .Fa base
  87 are sorted in ascending order according to
  88 a comparison function pointed to by
  89 .Fa compar ,
  90 which requires two arguments pointing to the objects being
  91 compared.
  92 .Pp
  93 The comparison function must return an integer less than, equal to, or
  94 greater than zero if the first argument is considered to be respectively
  95 less than, equal to, or greater than the second.
  96 .Pp
  97 The functions
  98 .Fn qsort
  99 and
 100 .Fn heapsort
 101 are
 102 .Em not
 103 stable, that is, if two members compare as equal, their order in
 104 the sorted array is undefined.
 105 The function
 106 .Fn mergesort
 107 is stable.
 108 .Pp
 109 The
 110 .Fn qsort
 111 function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm,
 112 a variant of partition-exchange sorting; in particular, see D.E. Knuth's
 113 Algorithm Q.
 114 .Fn Qsort
 115 takes O N lg N average time.
 116 This implementation uses median selection to avoid its
 117 O N**2 worst-case behavior.
 118 .Pp
 119 The
 120 .Fn heapsort
 121 function is an implementation of J.W.J. William's ``heapsort'' algorithm,
 122 a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H.
 123 .Fn Heapsort
 124 takes O N lg N worst-case time.
 125 Its
 126 .Em only
 127 advantage over
 128 .Fn qsort
 129 is that it uses almost no additional memory; while
 130 .Fn qsort
 131 does not allocate memory, it is implemented using recursion.
 132 .Pp
 133 The function
 134 .Fn mergesort
 135 requires additional memory of size
 136 .Fa nmemb *
 137 .Fa size
 138 bytes; it should be used only when space is not at a premium.
 139 .Fn Mergesort
 140 is optimized for data with pre-existing order; its worst case
 141 time is O N lg N; its best case is O N.
 142 .Pp
 143 Normally,
 144 .Fn qsort
 145 is faster than
 146 .Fn mergesort
 147 is faster than
 148 .Fn heapsort .
 149 Memory availability and pre-existing order in the data can make this
 150 untrue.
 151 .Sh RETURN VALUES
 152 The
 153 .Fn qsort
 154 function
 155 returns no value.
 156 .Pp
 157 .Rv -std heapsort mergesort
 158 .Sh ERRORS
 159 The
 160 .Fn heapsort
 161 and
 162 .Fn mergesort
 163 functions succeed unless:
 164 .Bl -tag -width Er
 165 .It Bq Er EINVAL
 166 The
 167 .Fa size
 168 argument is zero, or,
 169 the
 170 .Fa size
 171 argument to
 172 .Fn mergesort
 173 is less than
 174 .Dq "sizeof(void *) / 2" .
 175 .It Bq Er ENOMEM
 176 .Fn Heapsort
 177 or
 178 .Fn mergesort
 179 were unable to allocate memory.
 180 .El
 181 .Sh COMPATIBILITY
 182 Previous versions of
 183 .Fn qsort
 184 did not permit the comparison routine itself to call
 185 .Fn qsort 3 .
 186 This is no longer true.
 187 .Sh SEE ALSO
 188 .Xr sort 1 ,
 189 .Xr radixsort 3
 190 .Rs
 191 .%A Hoare, C.A.R.
 192 .%D 1962
 193 .%T "Quicksort"
 194 .%J "The Computer Journal"
 195 .%V 5:1
 196 .%P pp. 10-15
 197 .Re
 198 .Rs
 199 .%A Williams, J.W.J
 200 .%D 1964
 201 .%T "Heapsort"
 202 .%J "Communications of the ACM"
 203 .%V 7:1
 204 .%P pp. 347-348
 205 .Re
 206 .Rs
 207 .%A Knuth, D.E.
 208 .%D 1968
 209 .%B "The Art of Computer Programming"
 210 .%V Vol. 3
 211 .%T "Sorting and Searching"
 212 .%P pp. 114-123, 145-149
 213 .Re
 214 .Rs
 215 .%A Mcilroy, P.M.
 216 .%T "Optimistic Sorting and Information Theoretic Complexity"
 217 .%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
 218 .%V January 1992
 219 .Re
 220 .Rs
 221 .%A Bentley, J.L.
 222 .%T "Engineering a Sort Function"
 223 .%J "bentley@research.att.com"
 224 .%V January 1992
 225 .Re
 226 .Sh STANDARDS
 227 The
 228 .Fn qsort
 229 function
 230 conforms to
 231 .St -isoC .