日本語 man コマンド類 (ja-man-1.1j_5) と日本語 man ドキュメント (ja-man-doc-5.4 (5.4-RELEASE 用) など) をインストールすると、以下のような man コマンド閲覧、キーワード検索が コンソールからできるようになります。
4.11-RELEASE-K, 5.4-RELEASE-K, 5.5-RELEASE-K, 6.0-RELEASE-K から 6.4-RELEASE-K, 7.0-RELEASE-K から 7.4-RELEASE-K, 8.0-RELEASE-K から 8.4-RELEASE-K, 9.0-RELEASE-K から 9.3-RELEASE-K, 10.0-RELEASE-K から 10.3-RELEASE-K, 11.0-RELEASE-K から 11.4-RELEASE-K, 12.0-RELEASE-K, 12.1-RELEASE-K は、 プライベート版 (小金丸が編集してまとめたもの) ですが、 より多くの翻訳したファイルが含まれています。 (5.4-RELEASE-K から 6.4-RELEASE-K, 7.0-RELEASE-K から 7.4-RELEASE-K, 8.0-RELEASE-K から 8.4-RELEASE-K, 9.0-RELEASE-K から 9.3-RELEASE-K, 10.0-RELEASE-K から 10.3-RELEASE-K, 11.0-RELEASE-K から 11.4-RELEASE-K, 12.0-RELEASE-K から 12.3-RELEASE-K, 13.0-RELEASE-K から 13.2-RELEASE-K は、全翻訳済み)
13.3-STABLE-K, 15.0-CURRENT-K は現在、作成中で日々更新されています。
Table of Contents
QSORT(3) FreeBSD ライブラリ関数マニュアル QSORT(3)
名称
qsort, qsort_b, qsort_r, heapsort, heapsort_b, mergesort, mergesort_b --
ソート関数
ライブラリ
標準 C ライブラリ (libc, -lc)
書式
#include <stdlib.h>
void
qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
void
qsort_b(void *base, size_t nmemb, size_t size,
int (^compar)(const void *, const void *));
void
qsort_r(void *base, size_t nmemb, size_t size, void *thunk,
int (*compar)(void *, const void *, const void *));
int
heapsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
int
heapsort_b(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 *));
int
mergesort_b(void *base, size_t nmemb, size_t size,
int (^compar)(const void *, const void *));
解説
qsort() 関数は、修正された分割交換 (partition-exchange) ソート、またはク
イックソートです。heapsort() 関数は、修正された選択ソートです。
mergesort() 関数は、前もって存在する順序でデータのソートを対象とした指数
検索 (exponential search) を備えた修正されたマージソートです。
qsort() と heapsort() 関数は、base によって指される初期メンバである nmemb
オブジェクトの配列をソートします。各オブジェクトのサイズは、size によって
指定されます。mergesort() 関数は、同様に振る舞いますが、size が
``sizeof(void *) / 2'' より大きいことを必要とします。
配列 base の内容は、比較されているオブジェクトを指す 2 つの引数を必要とす
る、compar によって指される比較関数に従って昇順でソートされます。
比較関数は、最初の引数が 2 番目の引数より、それぞれ、小さい、等しいまたは
大きいなら、0 より小さい、等しいまたは大きい整数を返さなければなりませ
ん。
qsort_r() 関数は、compar を指す関数への最初の引数として変更せずに渡され
る、追加の引数 thunk を取ることを除いて、qsort() と同様に振る舞います。こ
れによって、比較関数は、グローバル変数を使用しないで追加のデータにアクセ
スでき、その結果、qsort_r() は、リエントラントでなければならない関数での
使用に適しています。qsort_b() 関数は、関数ポインタではなく、ブロックを取
ることを除いて、qsort() と同じように振る舞います。
qsort(), qsort_r() と heapsort() によって実装されたアルゴリズムは、安定し
ていません、すなわち、2 つのメンバが等しいなら、ソートされた配列の順序
は、不定になります。heapsort_b() 関数は、関数ポインタではなく、ブロックを
取ることを除いて、heapsort() と同じように振る舞います。mergesort() アルゴ
リズムは、安定しています。mergesort_b() 関数は、関数ポインタではなく、ブ
ロックを取ることを除いて、mergesort() と同じように振る舞います。
qsort() と qsort_r() 関数は、分割交換 (partition-exchange) ソートの一種で
ある、C.A.R. Hoare の ``クイックソート'' アルゴリズムを実装しています。特
に、D.E. Knuth の Algorithm Q を参照してください。quicksort は、O N lg N
の平均時間がかかります。この実装は、その O N**2 の最悪の場合の振る舞いを
回避するためにメディアン (median) 選択を使用します。
heapsort() 関数は、選択ソートの一種である、J.W.J. William の ``ヒープソー
ト'' アルゴリズムを実装しています。特に、D.E. Knuth の Algorithm H を参照
してください。heapsort は、O N lg N 最悪の場合の時間がかかります。qsort()
に勝る唯一の利点は、追加メモリをほとんど使わないことです。一方、qsort()
は、メモリを割り付けず、再帰 (リカージョン) を使用して実装されています。
関数 mergesort() は、サイズ nmemb * size バイトの追加メモリを必要としま
す。空間の使用にリスクがない場合に限り、使用されるべきです。mergesort()
関数は、前もって存在する順序でデータに最適化されます。その最悪の場合の時
間は、O N lg N です。その最良の場合は、O N です。
通常は、qsort() は、mergesort() より速く、それは、heapsort() より速いで
す。データのメモリの利用可能性と前もって存在する順序は、これを真実でなく
するかもしれません。
戻り値
qsort() と qsort_r() 関数は、値を返しません。
関数 heapsort() および mergesort() は、処理が成功すると値 0 を返します。
そうでない場合、値 -1 が返され、グローバル変数 errno にエラーを示す値が設
定されます。
使用例
qsort() を使用して、同じ場所に int 値の配列をソートし、次に、標準出力に
ソートされた配列を印刷するサンプルプログラムは、次の通りです:
#include <stdio.h>
#include <stdlib.h>
/*
* qsort(3) によって渡されたポインタを通して 'int' 値を比較する
* カスタムの比較関数.
*/
static int
int_compare(const void *p1, const void *p2)
{
int left = *(const int *)p1;
int right = *(const int *)p2;
return ((left > right) - (left < right));
}
/*
* 'int' 値の配列をソートして、標準出力にそれを印刷します.
*/
int
main(void)
{
int int_array[] = { 4, 5, 9, 3, 0, 1, 7, 2, 8, 6 };
size_t array_size = sizeof(int_array) / sizeof(int_array[0]);
size_t k;
qsort(&int_array, array_size, sizeof(int_array[0]), int_compare);
for (k = 0; k < array_size; k++)
printf(" %d", int_array[k]);
puts("");
return (EXIT_SUCCESS);
}
互換性
qsort() の以前のバージョンは、比較ルーチン自体が qsort(3) を呼び出すこと
を許可していませんでした。これは、もはや真実ではありません。
エラー
heapsort() と mergesort() 関数は、次の場合を除いて成功します:
[EINVAL] size 引数が 0 であるか、または mergesort() の size 引
数が ``sizeof(void *) / 2'' より小さい。
[ENOMEM] heapsort() または mergesort() 関数が、メモリを割り付け
られなかった。
関連項目
sort(1), radixsort(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 Computer Programming,
Vol. 3, pp. 114-123, 145-149, 1968.
McIlroy, P.M., "Optimistic Sorting and Information Theoretic Complexity",
Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, January 1992.
Bentley, J.L. and McIlroy, M.D., "Engineering a Sort Function",
Software--Practice and Experience, Vol. 23(11), pp. 1249-1265,
November 1993.
規格
qsort() 関数は、ISO/IEC 9899:1990 (``ISO C90'') に適合しています。
歴史
引数としてブロックを取るこれらの関数の変異型は、Mac OS X ではじめて登場し
ました。この実装は、David Chisnall によって作成されました。
FreeBSD 11.2 February 20, 2013 FreeBSD 11.2