| qsort.3 (120598) | qsort.3 (131504) |
|---|---|
| 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 --- 20 unchanged lines hidden (view full) --- 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 | 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 --- 20 unchanged lines hidden (view full) --- 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: head/lib/libc/stdlib/qsort.3 120598 2003-09-30 07:05:46Z tjr $ | 37.\" $FreeBSD: head/lib/libc/stdlib/qsort.3 131504 2004-07-02 23:52:20Z ru $ |
| 38.\" 39.Dd September 30, 2003 40.Dt QSORT 3 41.Os 42.Sh NAME 43.Nm qsort , qsort_r , heapsort , mergesort 44.Nd sort functions 45.Sh LIBRARY --- 98 unchanged lines hidden (view full) --- 144The 145.Fn mergesort 146algorithm is stable. 147.Pp 148The 149.Fn qsort 150and 151.Fn qsort_r | 38.\" 39.Dd September 30, 2003 40.Dt QSORT 3 41.Os 42.Sh NAME 43.Nm qsort , qsort_r , heapsort , mergesort 44.Nd sort functions 45.Sh LIBRARY --- 98 unchanged lines hidden (view full) --- 144The 145.Fn mergesort 146algorithm is stable. 147.Pp 148The 149.Fn qsort 150and 151.Fn qsort_r |
| 152functions are an implementation of C.A.R. Hoare's | 152functions are an implementation of C.A.R. 153Hoare's |
| 153.Dq quicksort 154algorithm, | 154.Dq quicksort 155algorithm, |
| 155a variant of partition-exchange sorting; in particular, see D.E. Knuth's 156Algorithm Q. | 156a variant of partition-exchange sorting; in particular, see 157.An D.E. Knuth Ns 's 158.%T "Algorithm Q" . |
| 157.Sy Quicksort 158takes O N lg N average time. 159This implementation uses median selection to avoid its 160O N**2 worst-case behavior. 161.Pp 162The 163.Fn heapsort | 159.Sy Quicksort 160takes O N lg N average time. 161This implementation uses median selection to avoid its 162O N**2 worst-case behavior. 163.Pp 164The 165.Fn heapsort |
| 164function is an implementation of J.W.J. William's | 166function is an implementation of 167.An "J.W.J. William" Ns 's |
| 165.Dq heapsort 166algorithm, | 168.Dq heapsort 169algorithm, |
| 167a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. | 170a variant of selection sorting; in particular, see 171.An "D.E. Knuth" Ns 's 172.%T "Algorithm H" . |
| 168.Sy Heapsort 169takes O N lg N worst-case time. 170Its 171.Em only 172advantage over 173.Fn qsort 174is that it uses almost no additional memory; while 175.Fn qsort --- 110 unchanged lines hidden --- | 173.Sy Heapsort 174takes O N lg N worst-case time. 175Its 176.Em only 177advantage over 178.Fn qsort 179is that it uses almost no additional memory; while 180.Fn qsort --- 110 unchanged lines hidden --- |