1

次のコードに問題があります。

class quicksort {
private:
  void _sort(double_it begin, double_it end)
  {
    if ( begin == end ) { return ; }
    double_it it = partition(begin, end, bind2nd(less<double>(), *begin)) ;
    iter_swap(begin, it-1);
    _sort(begin, it-1);
    _sort(it, end);
  }
public:
  quicksort  (){}
  void operator()(vector<double> & data)
  {
    double_it begin = data.begin();
    double_it end = data.end() ;
    _sort(begin, end);
  }
};

ただし、これは要素数が多すぎる場合には機能しません (10 000 要素では機能しますが、100 000 では機能しません)。

コード例:

int main()
{
  vector<double>v ;

  for(int i = n-1; i >= 0 ; --i)
    v.push_back(rand());  

  quicksort f;
  f(v);

  return 0;
}

STL パーティション機能はこのようなサイズでは動作しませんか? または、何か不足していますか？

助けてくれて本当にありがとうございます。

4

3 に答える 3

2

いくつかの問題があります。パーティションにピボットを含めないので、代わりに次の行を使用します。

double_it it = partition(begin + 1, end, bind2nd(less<double>(), *begin)) ;

また、私はあなたの将来のソートにピボットを含め続けないので、そうします

_sort(begin, it - 2);

it - 2代わりに、それ以下にならないように注意する必要があるbeginので、最初に確認してくださいit - 1 != begin。ピボットを継続的にソートする必要はありません。ピボットはすでに正しい場所にあります。これは、余分な不要な再帰を追加するだけです。

変更後でも、このコードではスタック オーバーフローの問題が発生する可能性があります。たとえば、このコードで既に並べ替えられた配列を並べ替えると、パフォーマンスは O(N^2) になり、N が非常に大きい場合はスタック オーバーフローが発生します。ランダムに選択されたピボットを使用すると、ソートされた配列の問題は本質的に解消されますが、配列がすべて同じ要素である場合は、依然として問題が発生する可能性があります。その場合、Bentley-McIlroy パーティショニングなどを使用するようにアルゴリズムを変更する必要があります。または、イントロソートに変更し、再帰の深さが非常に深くなったときにヒープソートに変更することもできます。

于 2010-05-26T13:57:54.520 に答える
1

doublt_it itの値に設定されていないことを確認しましたbeginか? それは行に問題を引き起こしiter_swap(begin, it-1);ます。

そうじゃない？

再帰が多すぎるため、#2 はスタック オーバーフローだと思います。特定のコンパイラは、多くの再帰ループを処理できません。100k でうまくいくかもしれませんが、10k で処理できます。

于 2010-05-26T13:36:58.063 に答える
0

次のコードを調べます。テンプレートを作成したりイテレータを使用したりせずに、すばやく書きましたが、アイデアは、巨大な配列をソートするのにクイックソートが問題ないことを証明することです(それはかなり明白です、へへへ)。

したがって、スタックオーバーフローやその他のコンパイラーの問題ではなく、アルゴリズムの観点からクイックソートに問題があります。つまり、何が原因なのかを常に理解し、「深い」問題を排除する必要がありますが、「浅い」問題は排除しないでください。

私のコードは、あなたのコードと同じ反復子アプローチを使用して簡単に書き直すことができることに注意してください (おそらく、追加のチェックが必要になるでしょうが、実装は簡単です)。

#include <vector>
#include <algorithm>
#include <utility>
#include <functional>

class sorter {
public:
   sorter(std::vector<int>& data) : data(data) { }

   void quicksort(int p, int r) {
      if (p < r) {
         int q = std::partition(data.begin() + p, data.begin() + r, std::bind2nd(std::less<int>(), data[r])) - data.begin();
         std::swap(data[q], data[r]);
         quicksort(p, q - 1);
         quicksort(q + 1, r);
      }
   }

   void sort() {
      quicksort(0, data.size() - 1);
   }

private:
   std::vector<int>& data;
};

int main() {
   size_t n = 1000000;
   std::vector<int> v;

   for(int i = n - 1; i >= 0 ; --i)
      v.push_back(rand());  

   sorter s(v);
   s.sort();

   return 0;
}

#編集

イテレータのものは次のような意味になります

class sorter {
public:
   typedef std::vector<int> data_type;
   sorter(std::vector<int>& data) : data(data) { }

   void quicksort(data_type::iterator p, data_type::iterator r) {
      data_type::iterator q = std::partition(p, r, std::bind2nd(std::less<int>(), *r));
      std::iter_swap(q, r);

      if (q != p)
         quicksort(p, q - 1);
      if (q != r)
         quicksort(q + 1, r);
   }

   void sort() {
      quicksort(data.begin(), data.end() - 1);
   }

private:
   std::vector<int>& data;
};
于 2010-05-26T14:57:04.283 に答える