0

安定な比較ソートを開発しています。
平均計算時間で最速なものを目指しています。
ソートされるデータ以外の格納領域が O(n) ぐらいは使用して良いと思っています。

安定でない比較ソートであれば、クイックソートが最速なのだと思っています。

glibc の qsort は
malloc に成功すれば 16*n バイトぐらい O(n) 格納領域を使用し
マージソートを実行します。なので安定です。

newlib の qsort は 30年近く使われているもので、安定でない比較ソートです。

そして、glibc と newlib の qsortを競争させると
ソートデータの条件により、勝ったり負けたりです。

ソートデータの条件は大きく分けて、次の4つがあると思います。

  1. 比較関数の重さ。
  2. 要素サイズの大きさ。
  3. 要素数。
  4. キー値の偏り。
    • A. 社員番号など同一キーがない場合
    • B. 都道府県コード(番号)など
    • C.男女など

安定な比較ソートに限って、平均計算時間で比較する場合、どのアルゴリズムが最高速と言えるのでしょうか?

例えば、次の中ではどれが速いのでしょうか?
ソート - Wikipedia

4
  • 参考にしてください research.preferred.jp/2011/10/tim-sort 2019年7月20日 9:16
  • 今回の質問の主題が分からないのですが、聞いているのは実装ではなくアルゴリズムということでよろしいですか?その場合 c タグは不適切そうです。また、ソートデータの条件というものはどのような理由で書かれているのですか?
    – PicoSushi
    2019年7月21日 2:49
  • 基本的には、アルゴリズムを聞いています。ただ、実際に走らせて時間を計りたいので言語cでの実装があると助かります。「ソートデータの条件」は、条件により答えが異なることも予想され得るので、条件とアルゴリズムのセットでの答えも有りと思い書きました。条件なしの答えがあればベストです。
    – t-kawa
    2019年7月21日 16:32
  • ソート対象のデータの順序をキーに加えれば、qsortのような安定でないソートも安定になると思います。 順序を生成する時間計算量や空間計算量(メモリの使用量)も増えますが、安定なソートで期待する速度性能がでない場合の選択肢のひとつだと考えます。 2019年11月7日 2:33

0

この質問に回答するには、ログインする必要があります。

のタグが付いた他の質問を参照する。