sorting - Cで多数の数値配列をソートするための良いライブラリはありますか?

Question

整数または浮動小数点数の大きな配列がある場合、(C での) 並べ替えに適したアルゴリズム/実装は何ですか?

編集には少し遅れています...しかし、私は正確さとスピードを探しています。

Answer 1

標準ライブラリの qsort() は良いです。

これらの場合、比較関数は簡単です。

int cmp_int(const void *a, const void *b)
{
    const int *ia = a;
    const int *ib = b;

    if (*ia < *ib)
        return -1;

    if (*ia > *ib)
        return 1;

    return 0;
}

int cmp_float(const void *a, const void *b)
{
    const float *fa = a;
    const float *fb = b;

    if (*fa < *fb)
        return -1;

    if (*fa > *fb)
        return 1;

    return 0;
}

(編集: a から b を減算することに基づくこれらのバージョンは、符号付きオーバーフロー動作に依存しているため、お勧めできません。)

Answer 2

数値の配列を並べ替えるには、基数並べ替えアルゴリズムを検討してください。適切に設計された場合、これらの並べ替えは GLIBC qsort() よりも優れたパフォーマンスを提供するはずです。

usort ライブラリには、すべての主要な C 数値型の型固有の実装が含まれています。

https://github.com/setjmp/usort

GLIBC qsort に対する基数ソートの速度の利点は、私の 64 ビット Intel ラップトップで N=1000000 の倍精度浮動小数点数で約 2.5 倍です。ただし、N が大きくなると、基数ソートは一定回数のデータ パスを必要とする線形時間アルゴリズムであるため、利点はさらに大きくなるはずです。

N が非常に小さい場合、同じコードがイントロソートまたは挿入ソートにディスパッチされます。

Answer 3

qsortを使用することは決して悪い考えではありません...数字について何か知っている場合を除きます。

基数ソートでタグ付けしました。どのくらいのメモリを投資する準備ができていますか? 数値は特定の範囲内ですか? 基数ソートを実行可能にするプロパティはありますか?

多くのメモリを使用したくない場合を除き、qsort は優れたオプションです。

Answer 4

現在取得している膨大な量の RAM を考えると、次のセットソートが可能です: 巨大な RAM ビット配列内の各数値のビットをマークし、RAM をスキャンしてそれらを読み戻します。マークおよびスキャン フェーズには、多くのハードウェア固有の最適化を適用できます。