| qsort.3 (107387) | qsort.3 (108037) |
|---|---|
| 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 107387 2002-11-29 15:57:50Z ru $ | 37.\" $FreeBSD: head/lib/libc/stdlib/qsort.3 108037 2002-12-18 12:45:11Z ru $ |
| 38.\" 39.Dd September 7, 2002 40.Dt QSORT 3 41.Os 42.Sh NAME 43.Nm qsort , qsort_r , heapsort , mergesort 44.Nd sort functions 45.Sh LIBRARY --- 46 unchanged lines hidden (view full) --- 92and 93.Fn heapsort 94functions sort an array of 95.Fa nmemb 96objects, the initial member of which is pointed to by 97.Fa base . 98The size of each object is specified by 99.Fa size . | 38.\" 39.Dd September 7, 2002 40.Dt QSORT 3 41.Os 42.Sh NAME 43.Nm qsort , qsort_r , heapsort , mergesort 44.Nd sort functions 45.Sh LIBRARY --- 46 unchanged lines hidden (view full) --- 92and 93.Fn heapsort 94functions sort an array of 95.Fa nmemb 96objects, the initial member of which is pointed to by 97.Fa base . 98The size of each object is specified by 99.Fa size . |
| 100.Fn Mergesort | 100The 101.Fn mergesort 102function |
| 101behaves similarly, but 102.Em requires 103that 104.Fa size 105be greater than 106.Dq "sizeof(void *) / 2" . 107.Pp 108The contents of the array --- 65 unchanged lines hidden (view full) --- 174does not allocate memory, it is implemented using recursion. 175.Pp 176The function 177.Fn mergesort 178requires additional memory of size 179.Fa nmemb * 180.Fa size 181bytes; it should be used only when space is not at a premium. | 103behaves similarly, but 104.Em requires 105that 106.Fa size 107be greater than 108.Dq "sizeof(void *) / 2" . 109.Pp 110The contents of the array --- 65 unchanged lines hidden (view full) --- 176does not allocate memory, it is implemented using recursion. 177.Pp 178The function 179.Fn mergesort 180requires additional memory of size 181.Fa nmemb * 182.Fa size 183bytes; it should be used only when space is not at a premium. |
| 182.Fn Mergesort | 184The 185.Fn mergesort 186function |
| 183is optimized for data with pre-existing order; its worst case 184time is O N lg N; its best case is O N. 185.Pp 186Normally, 187.Fn qsort 188is faster than 189.Fn mergesort 190is faster than --- 22 unchanged lines hidden (view full) --- 213argument is zero, or, 214the 215.Fa size 216argument to 217.Fn mergesort 218is less than 219.Dq "sizeof(void *) / 2" . 220.It Bq Er ENOMEM | 187is optimized for data with pre-existing order; its worst case 188time is O N lg N; its best case is O N. 189.Pp 190Normally, 191.Fn qsort 192is faster than 193.Fn mergesort 194is faster than --- 22 unchanged lines hidden (view full) --- 217argument is zero, or, 218the 219.Fa size 220argument to 221.Fn mergesort 222is less than 223.Dq "sizeof(void *) / 2" . 224.It Bq Er ENOMEM |
| 221.Fn Heapsort | 225The 226.Fn heapsort |
| 222or 223.Fn mergesort | 227or 228.Fn mergesort |
| 229functions |
|
| 224were unable to allocate memory. 225.El 226.Sh COMPATIBILITY 227Previous versions of 228.Fn qsort 229did not permit the comparison routine itself to call 230.Fn qsort 3 . 231This is no longer true. --- 45 unchanged lines hidden --- | 230were unable to allocate memory. 231.El 232.Sh COMPATIBILITY 233Previous versions of 234.Fn qsort 235did not permit the comparison routine itself to call 236.Fn qsort 3 . 237This is no longer true. --- 45 unchanged lines hidden --- |