RADIXSORT(3) FreeBSD ライブラリ関数マニュアル RADIXSORT(3)
名称
radixsort − 基数ソート |
ライブラリ
標準 C ライブラリ (libc, −lc) |
書式
#include <limits.h> int |
radixsort(const unsigned char **base, int nmemb, const unsigned char *table, unsigned endbyte); int |
sradixsort(const unsigned char **base, int nmemb, const unsigned char *table, unsigned endbyte); |
解説 |
radixsort() 関数と sradixsort() 関数は、基数ソート (ラディックスソート) を実装しています。 この関数は、初期メンバが base によって参照されているバイト文字列へのポイ ンタの配列をソートします。バイト文字列には任意の値を含められます。各文字 列の最後には、ユーザが定義した値 endbyte が付きます。 アプリケーションでは、 table 引数を指定することでソート順序を指定できま す。 NULL ではない table は、各バイト値のソートウェイトを含む、 UCHAR_MAX + 1 バイトの配列を参照している必要があります。文字列の終端バイトのソート ウェイトは、 0 か 255 (逆順ソート) でなければなりません。複数のバイトの ソートウェイトが等しいこともあります。 table 引数は、異なるキャラクタを等 しくソートするアプリケーションで便利です。たとえば A から Z の各々のウェ イトと a から z の各々のウェイトを等しくすると、大文字と小文字の区別をし ないソートができます。 table が NULL である場合、配列の内容は、参照するバ イト文字列の ASCII 順序に従って昇順にソートされます。この時、 endbyte の ソートウェイトは 0 です。 sradixsort() 関数は安定です。つまり、2 つの要素が等しい場合、これらの要素 の順序はソート済み配列でも変化しません。 sradixsort() 関数は、 nmemb ポイ ンタを収容するに十分なメモリを余分に使用します。 radixsort() 関数は不安定ですが、メモリを余分に使用しません。 この関数は、最上位バイト基数ソートの一種です。 D.E. Knuth のアルゴリズム R とセクション 5.2.5、エクササイズ 10 を参照してください。この関数には、 文字列のバイト数に比例した時間がかかります。 |
戻り値
関数 radixsort() は、処理が成功すると値 0 を返します。そうでない場合、値 -1 が返され、グローバル変数 errno が設定されてエラーを示します。 |
エラー
[EINVAL]
table の endbyte エレメントの値が 0 か 255 になってい ません。 sradixsort() 関数は、エラーが発生すると、ライブラリルーチン malloc(3) で 指定されているエラーを errno に設定することがあります。 関連項目 |
Knuth, D.E., " Sorting and Searching", The Art of ComputerProgramming, Vol. 3, pp. 170-178, 1968. Paige, R., " Three Partition Refinement Algorithms", SIAM J.Comput., No. 6, Vol. 16, 1987. McIlroy, P., " Computing Systems", Engineering Radix Sort, Vol.6:1, pp. 5-27, 1993.
歴史
radixsort() 関数は、 4.4BSD にはじめて登場しました。 FreeBSD 10.0 January 27, 1994 FreeBSD 10.0 |