\"      $NetBSD: qsort.3,v 1.16 2025/07/20 23:52:00 dholland Exp $
\"
\" Copyright (c) 1990, 1991, 1993
\"      The Regents of the University of California.  All rights reserved.
\"
\" This code is derived from software contributed to Berkeley by
\" the American National Standards Committee X3, on Information
\" Processing Systems.
\"
\" Redistribution and use in source and binary forms, with or without
\" modification, are permitted provided that the following conditions
\" are met:
\" 1. Redistributions of source code must retain the above copyright
\"    notice, this list of conditions and the following disclaimer.
\" 2. Redistributions in binary form must reproduce the above copyright
\"    notice, this list of conditions and the following disclaimer in the
\"    documentation and/or other materials provided with the distribution.
\" 3. Neither the name of the University nor the names of its contributors
\"    may be used to endorse or promote products derived from this software
\"    without specific prior written permission.
\"
\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
\" SUCH DAMAGE.
\"
\"     from: @(#)qsort.3        8.1 (Berkeley) 6/4/93
\"
Dd July 20, 2025
Dt QSORT 3
Os
Sh NAME
Nm qsort ,
Nm heapsort ,
Nm mergesort ,
Nm qsort_r ,
Nm heapsort_r ,
Nm mergesort_r
Nd sort functions
Sh LIBRARY
Lb libc
Sh SYNOPSIS
In stdlib.h
Ft void
Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
Ft void
Fn qsort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *, void *)" "void *cookie"
Ft int
Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
Ft int
Fn heapsort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *, void *)" "void *cookie"
Ft int
Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
Ft int
Fn mergesort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *, void *)" "void *cookie"
Sh DESCRIPTION
The
Fn qsort
function is a modified partition-exchange sort, or quicksort.
The
Fn heapsort
function is a modified selection sort.
The
Fn mergesort
function is a modified merge sort with exponential search
intended for sorting data with pre-existing order.
Pp
The
Fn qsort
and
Fn heapsort
functions sort an array of
Fa nmemb
objects, the initial member of which is pointed to by
Fa base .
The size of each object is specified by
Fa size .
Fn mergesort
behaves similarly, but
Em requires
that
Fa size
be greater than
Dq "sizeof(void *) / 2" .
Pp
The contents of the array
Fa base
are sorted in ascending order according to
a comparison function pointed to by
Fa compar ,
which requires two arguments pointing to the objects being
compared.
Pp
The comparison function must return an integer less than, equal to, or
greater than zero if the first argument is considered to be respectively
less than, equal to, or greater than the second.
Pp
The functions
Fn qsort
and
Fn heapsort
are
Em not
stable, that is, if two members compare as equal, their order in
the sorted array is undefined.
The function
Fn mergesort
is stable.
Pp
The
Fn qsort_r ,
Fn heapsort_r ,
and
Fn mergesort_r
functions pass an additional cookie argument through to the comparison
function.
Pp
The
Fn qsort
function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm,
a variant of partition-exchange sorting; in particular, see D.E. Knuth's
Algorithm Q.
Fn qsort
takes O N lg N average time.
This implementation uses median selection to avoid its
O N**2 worst-case behavior.
Pp
The
Fn heapsort
function is an implementation of J.W.J. William's ``heapsort'' algorithm,
a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H.
Fn heapsort
takes O N lg N worst-case time.
Its
Em only
advantage over
Fn qsort
is that it uses almost no additional memory; while
Fn qsort
does not allocate memory, it is implemented using recursion.
Pp
The function
Fn mergesort
requires additional memory of size
Fa nmemb *
Fa size
bytes; it should be used only when space is not at a premium.
Fn mergesort
is optimized for data with pre-existing order; its worst case
time is O N lg N; its best case is O N.
Pp
Normally,
Fn qsort
is faster than
Fn mergesort
is faster than
Fn heapsort .
Memory availability and pre-existing order in the data can make this
untrue.
Sh RETURN VALUES
The
Fn qsort
and
Fn qsort_r
functions
return no value.
Pp
Upon successful completion,
Fn heapsort ,
Fn mergesort
Fn heapsort_r ,
and
Fn mergesort_r
return 0.
Otherwise, they return \-1 and the global variable
Va errno
is set to indicate the error.
Sh COMPATIBILITY
Previous versions of
Fn qsort
did not permit the comparison routine itself to call
Fn qsort .
This is no longer true.
Sh ERRORS
The
Fn heapsort ,
Fn mergesort
Fn heapsort_r ,
and
Fn heapsort_r
functions succeed unless:
Bl -tag -width Er
It Bq Er EINVAL
The
Fa size
argument is zero, or,
the
Fa size
argument to
Fn mergesort
or
Fn mergesort_r
is less than
Dq "sizeof(void *) / 2" .
It Bq Er ENOMEM
Fn heapsort ,
Fn heapsort_r ,
Fn mergesort ,
or
Fn mergesort_r
were unable to allocate memory.
El
Sh SEE ALSO
Xr sort 1 ,
Xr radixsort 3
Rs
%A Hoare, C.A.R.
%D 1962
%T "Quicksort"
%J "The Computer Journal"
%V 5:1
%P pp. 10-15
Re
Rs
%A Williams, J.W.J
%D 1964
%T "Heapsort"
%J "Communications of the ACM"
%V 7:1
%P pp. 347-348
Re
Rs
%A Knuth, D.E.
%D 1968
%B "The Art of Computer Programming"
%V Vol. 3
%T "Sorting and Searching"
%P pp. 114-123, 145-149
Re
Rs
%A McIlroy, P.M.
%D 1993
%T "Optimistic Sorting and Information Theoretic Complexity"
%J "Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
%P pp. 467-474
Re
Rs
%A Bentley, J.L. and McIlroy, M.D.
%D 1993
%T "Engineering a Sort Function"
%J "Software-Practice and Experience"
%V Vol. 23
%P pp. 1249-1265
Re
Sh STANDARDS
The
Fn qsort
function conforms to
St -ansiC .
Sh HISTORY
The
Fn qsort_r ,
Fn heapsort_r ,
and
Fn mergesort_r
functions were added in
Nx 11.0 .
Pp
The
Fn qsort_r
function conforms to
St -p1003.1-2024 .

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.