QSORT

Section: C Library Functions (3)
索引 jman

BSD mandoc

索引

名称

qsort , heapsort , mergesort - ソート関数

索引

ライブラリ

Lb libc

索引

書式

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 *)

索引

解説

Fn qsort 関数は、パーティション交換ソートの修正版、ようするにクイックソートです。 Fn heapsort 関数は、選択ソートの修正版です。 Fn mergesort 関数は、既に並んでいる箇所のあるデータをソートする、指数検索によるマージソートの修正版です。

Fn qsort 関数と Fn heapsort 関数は、 Fa base によって初期メンバが指されている Fa nmemb オブジェクトの配列をソートします。各オブジェクトのサイズは、 Fa size で指定します。 Fn mergesort も同じように動作しますが、 Fa size は ``sizeof(void *) / 2'' より大きくなければなりません。

配列 Fa base の内容は、 Fa compar が指す比較関数に従って昇順でソートされます。この関数では、比較するオブジェクトを指す、2 つの引数が必要です。

比較関数は、最初の引数が次の引数より小さい場合は 0 より小さい整数、等しい場合は 0、大きい場合は 0 より大きい整数を戻す必要があります。

Fn qsort 関数と Fn heapsort 関数は不安定です。つまり 2 つのメンバが等しい場合、ソート済み配列内での順序は不定になります。 Fn mergesort 関数は安定です。

Fn qsort 関数は、パーティション交換ソートの一種である、C.A.R. Hoare の ``クイックソート'' アルゴリズムを実装しています。とくに D.E. Knuth のアルゴリズム Q を参照してください。 Fn qsort には、平均で O N lg N の時間がかかります。この実装では、メジアン選択を使用して、O N**2 という最悪なケースの動作を回避します。

Fn heapsort 関数は、選択ソートの一種である、J.W.J. William の ``ヒープソート'' アルゴリズムを実装しています。とくに D.E. Knuth のアルゴリズム H を参照してください。 Fn heapsort には、最悪のケースで O N lg N の時間がかかります。メモリをほとんど余分に使用しないという点のみが Fn qsort より優れています。一方、 Fn qsort はメモリを割り当てませんが、再帰を使用して実装されています。

Fn mergesort 関数では、 Fa nmemb * Fa size バイトのメモリが余分に必要となります。スペースに余裕がある場合のみに使用してください。 Fn mergesort は、既に並んでいる箇所のあるデータを扱うよう最適化されています。最悪のケースの時間は O N lg N で、最善のケースは O N です。

通常は、 Fn heapsort より Fn mergesort の方が速く、 Fn mergesort より Fn qsort の方が高速です。使用できるメモリ量や既に並んでいるデータ量により、この状況は変化します。

索引

戻り値

Fn qsort 関数は値を戻しません。

Rv -std heapsort mergesort

索引

エラー

Fn heapsort 関数と Fn mergesort 関数は、以下のような場合にエラーとなります。

Bq Er EINVAL: Fa size 引数が 0 であるか、 Fn mergesort の Fa size 引数が ``sizeof void * / 2'' より小さい場合。
Bq Er ENOMEM: Fn heapsort か Fn mergesort がメモリを割り当てられなかった場合。

索引