RADIXSORT(3) | FreeBSD Library Functions Manual | RADIXSORT(3) |
名称
radixsort, sradixsort — 基数ソートライブラリ
Standard C Library (libc, -lc)書式
#include < limits.h>#include < stdlib.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() 関数は、基数ソート (radix sort) の実装です。これらの関数は、 base によって参照される初期メンバである、バイト文字列へのポインタの配列をソートします。バイト文字列は、あらゆる値を含んでいます。各文字列の終りは、ユーザ指定の値 endbyte によって表示されます。
アプリケーションは、 table 引数を提供することによってソート順序を指定します。 NULL でないなら、 table は、各起こり得るバイト値のソートの重みを含んでいる UCHAR_MAX + 1 バイトの配列を参照しなければなりません。文字列の終りのバイトは、0 または 255 (逆の順序でソートするために) のソートの重みがなければなりません。 2 つ以上のバイトは、同じソートの重みがあります。 table 引数は、異なる文字を等しくソートしたいアプリケーションのために役に立ちます。例えば、a-z に関して A-Z に対して同じ重みがあるテーブルを提供することは、大文字小文字を区別しないソートの結果となります。 table が NULL であるなら、配列の内容は、それらが参照するバイト文字列の ASCII 順序にしたがって昇順でソートされ、 endbyte は、0 のソートの重みがあります。
sradixsort() 関数は、安定しています (stable)、すなわち、2 つの要素が等しいとして比較するなら、ソートされる配列の順序は、変更されません。 sradixsort() 関数は、 nmemb ポインタを保持するのに十分な追加のメモリを使用します。
radixsort() 関数は、安定していません (not stable) が、追加のメモリを使用しません。
これらの関数は、最上位バイト基数ソートの一種です。特に Algorithm R and section 5.2.5, exercise 10 (D.E. Knuth の Algorithm R のセクション 5.2.5、練習 10) を参照してください。それらは、文字列中のバイトの数に比例した線形の時間がかかります。
's戻り値
The radixsort() function returns the value 0 if successful; otherwise the value -1 is returned and the global variable errno is set to indicate the error.エラー
- [ EINVAL]
- table の endbyte 要素の値が、0 または 255 ではありません。
さらに、 sradixsort() 関数は、失敗し、ライブラリルーチン malloc(3) で明記されたエラーのいずれかを errno に設定します。
関連項目
sort(1), qsort(3)Knuth, D.E., Sorting and Searching, The Art of Computer Programming, 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 ではじめて登場しました。January 27, 1994 | FreeBSD |