xref: /illumos-gate/usr/src/man/man3c/qsort.3c (revision 8c9d84f540d1f878958d02bef1d5c221fc8d30c0)

.\"
.\" The contents of this file are subject to the terms of the
.\" Common Development and Distribution License (the "License").
.\" You may not use this file except in compliance with the License.
.\"
.\" You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
.\" or http://www.opensolaris.org/os/licensing.
.\" See the License for the specific language governing permissions
.\" and limitations under the License.
.\"
.\" When distributing Covered Code, include this CDDL HEADER in each
.\" file and include the License file at usr/src/OPENSOLARIS.LICENSE.
.\" If applicable, add the following below this CDDL HEADER, with the
.\" fields enclosed by brackets "[]" replaced with your own identifying
.\" information: Portions Copyright [yyyy] [name of copyright owner]
.\"
.\"
.\" Copyright 1989 AT&T
.\" Copyright (c) 2002, Sun Microsystems, Inc.  All Rights Reserved
.\" Copyright 2020 Oxide Computer Company
.\"
.Dd November 15, 2023
.Dt QSORT 3C
.Os
.Sh NAME
.Nm qsort ,
.Nm qsort_r
.Nd quick sort
.Sh SYNOPSIS
.In stdlib.h
.Ft void
.Fo qsort
.Fa "void *base"
.Fa "size_t nel"
.Fa "size_t width"
.Fa "int (*compar)(const void *, const void *)"
.Fc
.Ft void
.Fo qsort_r
.Fa "void *base"
.Fa "size_t nel"
.Fa "size_t width"
.Fa "int (*compar_arg)(const void *, const void *, void *)"
.Fa "void *arg"
.Fc
.Sh DESCRIPTION
The
.Fn qsort
function is an implementation of the quick-sort algorithm.
It sorts a table of data in place.
The contents of the table are sorted in ascending order according to the
user-supplied comparison function.
.Pp
The
.Fa base
argument points to the element at the base of the table.
The
.Fa nel
argument is the number of elements in the table.
The
.Fa width
argument specifies the size of each element in bytes.
The
.Fa compar
argument is the name of the comparison function, which is called with two
arguments that point to the elements being compared.
The comparison function need not compare every byte, so arbitrary data may be
contained in the elements in addition to the values being compared.
.Pp
The function must return an integer less than, equal to, or greater than zero
to indicate if the first argument is to be considered less than, equal to, or
greater than the second argument.
.Pp
The contents of the table are sorted in ascending order according to the user
supplied comparison function.
The relative order in the output of two items that compare as equal is
unpredictable.
.Pp
The
.Fn qsort_r
function behaves similarly to the
.Fn qsort
function, except that its comparison function,
.Fn compar_arg ,
takes an extra argument which is the
.Fn qsort_r
argument
.Fa arg .
This allows one to avoid global data in the comparison function, unlike
with the
.Fn qsort
function.
.Pp
The
.Fn qsort
and
.Fn qsort_r
functions safely allow concurrent access by multiple threads
to disjoint data, such as overlapping subtrees or tables.
.Sh EXAMPLES
.Sy Example 1
Program sorts.
.Pp
The following program sorts a simple array:
.Bd -literal
#include <stdlib.h>
#include <stdio.h>

static int
intcompare(const void *p1, const void *p2)
{
    int i = *((int *)p1);
    int j = *((int *)p2);

    if (i > j)
        return (1);
    if (i < j)
        return (-1);
    return (0);
}

int
main()
{
    int i;
    int a[10] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    size_t nelems = sizeof (a) / sizeof (int);

    qsort((void *)a, nelems, sizeof (int), intcompare);

    for (i = 0; i < nelems; i++) {
        (void) printf("%d ", a[i]);
    }

    (void) printf("\en");
    return (0);
}
.Ed
.Sh INTERFACE STABILITY
.Sy Standard
.Sh MT-LEVEL
.Sy MT-Safe
.Sh SEE ALSO
.Xr sort 1 ,
.Xr bsearch 3C ,
.Xr lsearch 3C ,
.Xr string 3C ,
.Xr attributes 7 ,
.Xr standards 7