QSORT(3) FreeBSD ライブラリ関数マニュアル QSORT(3)
名称
qsort, heapsort, mergesort − ソート関数 |
ライブラリ
標準 C ライブラリ (libc, −lc) |
書式
#include <stdlib.h> void |
qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)); int |
heapsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)); int |
mergesort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)); |
解説 |
qsort() 関数は、パーティション交換ソートの修正版、ようするにクイックソー トです。 heapsort() 関数は、選択ソートの修正版です。 mergesort() 関数は、 既に並んでいる箇所のあるデータをソートする、指数検索によるマージソートの 修正版です。 qsort() 関数と heapsort() 関数は、 base によって初期メンバが指されている nmemb オブジェクトの配列をソートします。各オブジェクトのサイズは、 size で指定します。 mergesort() も同じように動作しますが、 size は ‘‘sizeof(void *) / 2’’ より大きくなければなりません。 配列 base の内容は、 compar が指す比較関数に従って昇順でソートされます。 この関数では、比較するオブジェクトを指す、2 つの引数が必要です。 比較関数は、最初の引数が次の引数より小さい場合は 0 より小さい整数、等しい 場合は 0、大きい場合は 0 より大きい整数を戻す必要があります。 qsort() 関数と heapsort() 関数は不安定です。つまり 2 つのメンバが等しい場 合、ソート済み配列内での順序は不定になります。 mergesort() 関数は安定で す。 qsort() 関数は、パーティション交換ソートの一種である、C.A.R. Hoare の ‘‘ クイックソート’’ アルゴリズムを実装しています。とくに D.E. Knuth のアルゴ リズム Q を参照してください。 qsort() には、平均で O N lg N の時間がかか ります。この実装では、メジアン選択を使用して、O N**2 という最悪なケースの 動作を回避します。 heapsort() 関数は、選択ソートの一種である、J.W.J. William の ‘‘ヒープソー ト’’ アルゴリズムを実装しています。とくに D.E. Knuth のアルゴリズム H を 参照してください。 heapsort() には、最悪のケースで O N lg N の時間がかか ります。メモリをほとんど余分に使用しないという点のみが qsort() より優れて います。一方、 qsort() はメモリを割り当てませんが、再帰を使用して実装され ています。 mergesort() 関数では、 nmemb * size バイトのメモリが余分に必要となりま す。スペースに余裕がある場合のみに使用してください。 mergesort() は、既に 並んでいる箇所のあるデータを扱うよう最適化されています。最悪のケースの時 間は O N lg N で、最善のケースは O N です。 通常は、 heapsort() より mergesort() の方が速く、 mergesort() より qsort() の方が高速です。使用できるメモリ量や既に並んでいるデータ量によ り、この状況は変化します。 |
戻り値
qsort() 関数は値を戻しません。 関数 heapsort() および mergesort() は、処理が成功すると値 0 を返します。 そうでない場合、値 -1 が返され、グローバル変数 errno が設定されてエラーを 示します。 |
エラー
heapsort() 関数と mergesort() 関数は、以下のような場合にエラーとなりま す。 |
[EINVAL]
size 引数が 0 であるか、 mergesort() の size 引数が ‘‘sizeof void * / 2’’ より小さい場合。 [ENOMEM] 互換性 |
旧バージョンの qsort() では、比較ルーチンが qsort(3) を呼び出すことはでき ませんでした。現在は呼び出せます。 |
関連項目
Hoare, C.A.R., " Quicksort", The Computer Journal, 5:1, pp.10-15, 1962. Williams, J.W.J, " Heapsort", Communications of the ACM, 7:1, pp. 347-348, 1964. Knuth, D.E., " Sorting and Searching", The Art of ComputerProgramming, Vol. 3, pp. 114-123, 145-149, 1968. Mcilroy, P.M., " Optimistic Sorting and Information TheoreticComplexity", Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, January 1992. Bentley, J.L., " Engineering a Sort Function", bentley@research.att.com, January 1992.
規格
qsort() 関数は、 ISO/IEC 9899:1990 (‘‘ISO C89’’) に適合しています。 FreeBSD 10.0 June 4, 1993 FreeBSD 10.0 |