5

私は簡単なクイックソートの実装を持っています:

template <typename IteratorType>
void quicksort(IteratorType begin, IteratorType end)
{
  if (begin != end)
  {
    const auto pivot = *(begin + distance(begin, end) / 2);
    const IteratorType sep = std::partition(begin, end, [pivot](typename IteratorType::value_type v){ return (v < pivot); });

    if (sep != begin)
    {
      quicksort(begin, sep);
    }

    if (sep != end)
    {
      quicksort(sep + 1, end);
    }
  }
}

std::sort1000000要素の配列でテストすると、再帰で死ぬことがある前に、約30ミリ秒かかりますが、永遠に（6300ミリ秒）かかります。

確かに、私のくだらない実装が ほど速くなるとは思っていませんがstd::sort、どうしてそんなに大きな違いがあるのでしょうか?

std::sort単純なクイックソート（イントロソートだと思います）よりも複雑なものを使用して、再帰レベルなどを行き過ぎないようにすることを理解しています。しかし、それでも、そのような大きな違いを説明できる明らかな何かが欠けていますか?

矢印のサイズを変化させると、差分係数が一定ではないことがわかります。実際には のように大きくなるように見えn²ます。

4

2 に答える 2

1

最初に、より適切なピボット選択を確認し (通常、中央値 3 が使用されます)、再帰の分岐を 1 つ削除して、スタック スペースを節約します。

ピボットの選択は、N*log(n) と N^2 の違いを生むため、アルゴリズム全体のパフォーマンスに最も大きな影響を与えます。

于 2013-04-28T14:28:23.353 に答える
1

コードが正しいと仮定すると (クイックソートはトリッキーになる可能性があります)、大きな違いは、要素の数が少ない場合に高速なソートを使用していないことだと思います。たとえば、ソートする要素の数が小さい数よりも少ない場合、選択ソートを使用するのが一般的です。

私はそれについて何も知らないことを率直に認めますが、その危険な C++11 コードも私を疑っています。

于 2013-04-28T14:10:45.407 に答える