1

クイックソートのコードは次のとおりです。

typedef struct tagDataPair {
    int c_value;
    float error;
} DataPair;

void SortByErrorQS(std::vector<DataPair>& points, int left, int right)
{
    std::vector<int> stack;
    stack.push_back(left);
    stack.push_back(right);
    while(stack.size() > 0)
    {
        right = stack.back();
        stack.pop_back();
        left = stack.back();
        stack.pop_back();

        float pivot = (points.at(left).error + points.at(right).error + points.at((left + right)>>1).error)/3;
        int i = left, j = right;
        DataPair temp;
        while(i < j)
        {
            while(points.at(i).error <= pivot && (i <= right))
                ++i;
            while(points.at(j).error > pivot && (j > left))
                --j;
            if(i <= j)
            {
                temp = points[i];
                points[i] = points[j];
                points[j] = temp;
                i++; j--;
            }
        }

        if(left < j)
        {
            stack.push_back(left);
            stack.push_back(j);
        }
        if(i < right)
        {
            stack.push_back(i);
            stack.push_back(right);
        }
    }
}

何らかの理由で、これは無限ループに陥っており、何が問題になっているのか、あるいはその理由を理解できません。誰かがここで何が起こっているのかポインターを手伝ってくれますか？

4

1 に答える 1

3

構造体で使用std::sortするDataPairために、カスタムコンパレータを提供できます。C ++ 11では、これはラムダ関数を使用して実行できます。

std::sort(points.begin(), points.end(), [](const DataPair& a, const DataPair& b) {
  return a.error < b.error;
});

これにより、DataPairsが。の昇順で並べ替えられますerror。

C ++ 03のアプローチは、比較機能を提供することです。

bool compare(const DataPair& a, const DataPair& b)
{
  return a.error < b.error;
}

std:sort(points.begin(), points.end(), compare);

の複雑さはでstd::sortあることが保証されていますO(NlogN)。一般的な実装では、クイックソートまたはイントロソートを使用します。

于 2013-02-21T18:10:58.747 に答える