EN JA
RADIXSORT(3)
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) が、追加のメモリを使用しません。

これらの関数は、最上位バイト基数ソートの一種です。特に D.E. Knuth's Algorithm R and section 5.2.5, exercise 10 (D.E. Knuth の Algorithm R のセクション 5.2.5、練習 10) を参照してください。それらは、文字列中のバイトの数に比例した線形の時間がかかります。

戻り値

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]
tableendbyte 要素の値が、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