EN JA
QSORT(3)
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 の“クイックソート”アルゴリズムを実装しています。特に、 D.E. KnuthAlgorithm Q を参照してください。 quicksort は、O N lg N の平均時間がかかります。この実装は、その O N**2 の最悪の場合の振る舞いを回避するためにメディアン (median) 選択を使用します。

heapsort() 関数は、選択ソートの一種である、 J.W.J. William の“ヒープソート”アルゴリズムを実装しています。特に、 D.E. KnuthAlgorithm 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