1

演習として、テンプレートにクイックソート アルゴリズムを実装しました。要素数が少ない (最大約 760) ベクトルでは「正常に動作」しますが、要素数が多い場合は seqfault が発生します。誰かが私が間違っていることを教えてもらえますか:

template< typename Vector, typename VecElem > void qsort(Vector *pv)
{
    if (pv->size()<=1) return;

    VecElem p;
    Vector *pvl=new Vector,*pvr=new Vector;

    p = pv->back();
    pv->pop_back();
    pvr->push_back(p);
    for (auto it=pv->begin();it!=pv->end();it++)
    {
        if (*it < p) pvl->push_back(*it);
        else pvr->push_back(*it);
    }
    qsort<Vector,VecElem>(pvl);
    qsort<Vector,VecElem>(pvr);
    if (pvl->size()) *pv = *pvl;
    if (pvr->size()) std::copy(pvr->begin(), pvr->end(), std::back_inserter(*pv));
    delete pvl;
    delete pvr;
}
4

1 に答える 1

4

他の人が指摘したように、たとえば昇順のデータをソートする場合、実装は効率的ではありません。ただし、これはセグメンテーション違反の理由ではありません。コードの問題は、分割フェーズでピボット要素を除外していないことです。

単純に、2 つの同一要素 ({0,0} など) だけで構成されるベクトルを並べ替えてみてください。無限ループになります。

この問題を解決するには、両方のベクトルを並べ替えた後でピボット要素を挿入します。

多分これはうまくいくでしょう（少なくともスタックオーバーフローを修正します）：

pvr->push_back(p); // remove this line

// and insert it later...
qsort<Vector,VecElem>(pvl);
qsort<Vector,VecElem>(pvr);
pvl->push_back(p); // this line is new
于 2012-12-28T18:51:28.957 に答える