QSORT(3) | FreeBSD Library Functions Manual | QSORT(3) |
名称
qsort, qsort_r, heapsort, mergesort — ソート関数ライブラリ
Standard C Library (libc, -lc)書式
#include < stdlib.h> void
qsort( 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
mergesort( 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(), qsort_r() と heapsort() によって実装されたアルゴリズムは、安定して いません、すなわち、2 つのメンバが等しいなら、ソートされた配列の順序は、不定になります。 mergesort() アルゴリズムは、安定しています。
qsort() と qsort_r() 関数は、分割交換 (partition-exchange) ソートの一種である、C.A.R. Hoare の“クイックソート”アルゴリズムを実装しています。特に、 Algorithm Q を参照してください。 quicksort は、O N lg N の平均時間がかかります。この実装は、その O N**2 の最悪の場合の振る舞いを回避するためにメディアン (median) 選択を使用します。
のheapsort() 関数は、選択ソートの一種である、 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() 関数は、値を返しません。
The heapsort() and 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.
使用例
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 }; const 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”) に適合しています。February 20, 2013 | FreeBSD |