tail head cat sleep
QR code linking to this page

manページ  — RADIXSORT

名称

radixsort – 基数ソート

内容

ライブラリ

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() 関数は、基数ソート (ラディックスソート) を実装しています。

この関数は、初期メンバが 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 を参照してください。 この関数には、文字列のバイト数に比例した時間がかかります。

戻り値

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., The Art of Computer Programming, pp. 170-178, Sorting and Searching, Vol. 3, 1968.

Paige, R., No. 6, SIAM J. Comput., Three Partition Refinement Algorithms, Vol. 16, 1987.

McIlroy, P., Engineering Radix Sort, pp. 5-27, Computing Systems, Vol. 6:1, 1993.

歴史

radixsort() 関数は、 BSD 4.4 にはじめて登場しました。

RADIXSORT (3) January 27, 1994

tail head cat sleep
QR code linking to this page


このマニュアルページサービスについてのご意見は Ben Bullock にお知らせください。 Privacy policy.