RADIXSORT

Section: C Library Functions (3)
索引 jman

BSD mandoc

索引

名称

radixsort - 基数ソート

索引

ライブラリ

Lb libc

索引

書式

In limits.h In stdlib.h Ft int Fn radixsort const unsigned char **base int nmemb const unsigned char *table unsigned endbyte Ft int Fn sradixsort const unsigned char **base int nmemb const unsigned char *table unsigned endbyte

索引

解説

Fn radixsort 関数と Fn sradixsort 関数は、基数ソート (ラディックスソート) を実装しています。

この関数は、初期メンバが Fa base によって参照されているバイト文字列へのポインタの配列をソートします。バイト文字列には任意の値を含められます。各文字列の最後には、ユーザが定義した値 Fa endbyte が付きます。

アプリケーションでは、 Fa table 引数を指定することでソート順序を指定できます。 NULL ではない Fa table は、各バイト値のソートウェイトを含む、 UCHAR_MAX + 1 バイトの配列を参照している必要があります。文字列の終端バイトのソートウェイトは、 0 か 255 (逆順ソート) でなければなりません。複数のバイトのソートウェイトが等しいこともあります。 Fa table 引数は、異なるキャラクタを等しくソートするアプリケーションで便利です。たとえば A から Z の各々のウェイトと a から z の各々のウェイトを等しくすると、大文字と小文字の区別をしないソートができます。 Fa table が NULL である場合、配列の内容は、参照するバイト文字列の ASCII 順序に従って昇順にソートされます。この時、 Fa endbyte のソートウェイトは 0 です。

Fn sradixsort 関数は安定です。つまり、2 つの要素が等しい場合、これらの要素の順序はソート済み配列でも変化しません。 Fn sradixsort 関数は、 Fa nmemb ポインタを収容するに十分なメモリを余分に使用します。

Fn radixsort 関数は不安定ですが、メモリを余分に使用しません。

この関数は、最上位バイト基数ソートの一種です。 D.E. Knuth のアルゴリズム R とセクション 5.2.5、エクササイズ 10 を参照してください。この関数には、文字列のバイト数に比例した時間がかかります。

索引