c - C: ソート方法の分析

Question

私は、次の署名を持つさまざまな並べ替えアルゴリズムをたくさん持っています。

void <METHOD>_sort_ints(int * array, const unsigned int ARRAY_LENGTH);

経験的な比較を行う目的で使用できるソート用のテストスイートはありますか?

Answer 1

この詳細な説明は、役立つと思われる多数の関連Webページへのリンクだけでなく、並べ替えアルゴリズムをテストするための有用な入力データのセットについても説明しています（理由についてはリンクされたページを参照してください）。要約：

1. 完全にランダムに再シャッフルされた配列
2. すでにソートされた配列
3. すでに逆順の配列でソートされています
4. チェーンソーアレイ
5. 同一要素の配列
6. N個の順列（サイズの0.1から10％のN）で既にソートされた配列
7. N個の順列を持つ逆順の配列ですでにソートされている配列
8. 重複（または閉じる）キーで正規分布しているデータ（安定ソートのみ）
9. 疑似ランダムデータ（S＆P500またはその他の10年間のインデックスの毎日の値は、ここで設定するのに適したテストになる可能性があります。Yahoo.comから入手できます）

Answer 2

このサイトでは、4つのグループを使用したさまざまな並べ替えアルゴリズムを示しています。http： //www.sorting-algorithms.com/

Normanの回答の4つのグループに加えて、数値にいくつかの類似点がある数値のコレクションを使用して並べ替えアルゴリズムを確認する必要があります。

• すべての整数は一意です
• コレクション全体で同じ整数
• いくつかの一意のキー

コレクション内の要素の数を変更することも、1K、1M、1Gなどで各アルゴリズムをチェックして、そのアルゴリズムのメモリへの影響を確認することをお勧めします。

Answer 3

sortperf.pyには、厳選された一連のベンチマーク テスト ケースがあり、ここにあるエッセイをサポートするために使用され、何年も前に Python で timsort THE SORT を作成しました。Josh Block のおかげで、ついに Java も timsort に移行する可能性があることに注意してください (こちらを参照)。)、そのため、彼らは独自のバージョンのベンチマーク テスト ケースを作成していると思いますが、それへの参照を簡単に見つけることができません。(timsort は、安定した適応型の反復型の自然なマージソートのバリアントであり、「データ移動」が比較的安価な Python や Java などのオブジェクトへの参照セマンティクスを備えた言語に特に適しています [[これまでに移動されたものはすべて参照またはポインターであるため、 、無制限のサイズのブロブではありません;-)]]、しかし比較は比較的コストがかかる可能性があります[[比較関数の複雑さに上限がないため--しかし、これはカスタムを介してソートをカスタマイズできる言語に当てはまります比較またはキー抽出関数]])。