.\" 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. All advertising materials mentioning features or use of this software
.\"    must display the following acknowledgement:
.\"	This product includes software developed by the University of
.\"	California, Berkeley and its contributors.
.\" 4. 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.
.\"
.\"     @(#)qsort.3	8.1 (Berkeley) 6/4/93
.\" %FreeBSD: src/lib/libc/stdlib/qsort.3,v 1.4.2.4 2001/08/31 10:15:15 ru Exp %
.\" $FreeBSD$
.\"
.Dd June 4, 1993
.Dt QSORT 3
.Os
.Sh 名称
.Nm qsort , heapsort , mergesort
.Nd ソート関数
.Sh ライブラリ
.Lb libc
.Sh 書式
.Fd #include <stdlib.h>
.Ft void
.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
.Ft int
.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
.Ft int
.Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
.Sh 解説
.Fn qsort
関数は、パーティション交換ソートの修正版、ようするにクイックソートです。 
.Fn heapsort
関数は、選択ソートの修正版です。
.Fn mergesort
関数は、既に並んでいる箇所のあるデータをソートする、
指数検索によるマージソートの修正版です。
.Pp
.Fn qsort
関数と
.Fn heapsort
関数は、
.Fa base
によって初期メンバが指されている
.Fa nmemb
オブジェクトの配列をソートします。
各オブジェクトのサイズは、
.Fa size
で指定します。
.Fn mergesort
も同じように動作しますが、
.Fa size
は
.Dq "sizeof(void *) / 2"
より大きくなければなりません。
.Pp
配列
.Fa base
の内容は、
.Fa compar
が指す比較関数に従って昇順でソートされます。
この関数では、比較するオブジェクトを指す、2 つの引数が必要です。
.Pp
比較関数は、最初の引数が次の引数より小さい場合は 0 より小さい整数、
等しい場合は 0、大きい場合は 0 より大きい整数を戻す必要があります。 
.Pp
.Fn qsort
関数と
.Fn heapsort
関数は不安定です。
つまり 2 つのメンバが等しい場合、ソート済み配列内での順序は不定になります。 
.Fn mergesort
関数は安定です。
.Pp
.Fn qsort
関数は、パーティション交換ソートの一種である、C.A.R. Hoare の
``クイックソート'' アルゴリズムを実装しています。
とくに D.E. Knuth のアルゴリズム Q を参照してください。
.Fn qsort
には、平均で
O N lg N
の時間がかかります。
この実装では、メジアン選択を使用して、O N**2 という
最悪なケースの動作を回避します。
.Pp
.Fn heapsort
関数は、選択ソートの一種である、J.W.J. William の
``ヒープソート'' アルゴリズムを実装しています。
とくに D.E. Knuth のアルゴリズム H を参照してください。
.Fn heapsort
には、最悪のケースで
O N lg N
の時間がかかります。
メモリをほとんど余分に使用しないという点のみが
.Fn qsort
より優れています。
一方、
.Fn qsort
はメモリを割り当てませんが、再帰を使用して実装されています。
.Pp
.Fn mergesort
関数では、
.Fa nmemb *
.Fa size
バイトのメモリが余分に必要となります。
スペースに余裕がある場合のみに使用してください。 
.Fn mergesort
は、既に並んでいる箇所のあるデータを扱うよう最適化されています。
最悪のケースの時間は O N lg N で、最善のケースは O N です。
.Pp
通常は、
.Fn heapsort
より
.Fn mergesort
の方が速く、
.Fn mergesort
より
.Fn qsort
の方が高速です。
使用できるメモリ量や既に並んでいるデータ量により、この状況は変化します。 
.Sh 戻り値
.Fn qsort
関数は値を戻しません。
.Pp
.Rv -std heapsort mergesort
.Sh エラー
.Fn heapsort
関数と
.Fn mergesort
関数は、以下のような場合にエラーとなります。
.Bl -tag -width Er
.It Bq Er EINVAL
.Fa size
引数が 0 であるか、
.Fn mergesort
の
.Fa size
引数が
.Dq "sizeof void * / 2"
より小さい場合。
.It Bq Er ENOMEM
.Fn heapsort
か
.Fn mergesort
がメモリを割り当てられなかった場合。
.El
.Sh 互換性
旧バージョンの
.Fn qsort
では、比較ルーチンが
.Fn qsort 3
を呼び出すことはできませんでした。
現在は呼び出せます。
.Sh 関連項目
.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.
.%T "Optimistic Sorting and Information Theoretic Complexity"
.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
.%V January 1992
.Re
.Rs
.%A Bentley, J.L.
.%T "Engineering a Sort Function"
.%J "bentley@research.att.com"
.%V January 1992
.Re
.Sh 規格
.Fn qsort
関数は、
.St -isoC
に適合しています。