tail head cat sleep
QR code linking to this page

manページ  — QSORT

名称

qsort – ソート関数

内容

ライブラリ

Standard C Library (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() 関数は値を戻しません。

The heapsortand mergesort functions return the value 0 if successful; otherwise the value -1 is returned and the global variable errno is set to indicate the error.

エラー

heapsort() 関数と mergesort() 関数は、以下のような場合にエラーとなります。
[EINVAL]
  size 引数が 0 であるか、 mergesort()size 引数が "sizeof void * / 2" より小さい場合。
[ENOMEM]
  heapsort()mergesort() がメモリを割り当てられなかった場合。

互換性

旧バージョンの qsort() では、比較ルーチンが qsort(3) を呼び出すことはできませんでした。 現在は呼び出せます。

関連項目

sort(1), radixsort(3)

Hoare, C.A.R., The Computer Journal, pp. 10-15, Quicksort, 5:1, 1962.

Williams, J.W.J, Communications of the ACM, pp. 347-348, Heapsort, 7:1, 1964.

Knuth, D.E., The Art of Computer Programming, pp. 114-123, 145-149, Sorting and Searching, Vol. 3, 1968.

Mcilroy, P.M., Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Optimistic Sorting and Information Theoretic Complexity, January 1992,

Bentley, J.L., bentley@research.att.com, Engineering a Sort Function, January 1992,

規格

qsort() 関数は、 ISO/IEC 9899:1990 ("ISO C90") に適合しています。

QSORT (3) June 4, 1993

tail head cat sleep
QR code linking to this page


このマニュアルページサービスについてのご意見は Ben Bullock にお知らせください。 Privacy policy.

VI = Virtually Incomprehensible.