c++ - カウントソート無限ループ

Question

カウントソート関数を書いていますが、それを実行すると、「filename.exeが動作を停止しました」というウィンドウがポップアップします。forデバッグ後、2 番目のループでスタックしているように見えます。本当に混乱するのはmaxInt、130000 より大きい数値に設定すると機能するが、130000 以下の数値に設定するとエラーメッセージが表示されることです。並べ替えに使用しているファイルには、約 20 個の数字しかありません。

#include <iterator>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iostream>
using namespace std;

std::string file = "";
std::vector<int> numbers;

void CountingSort(vector<int> &numbers);

int main()
{
    std::cout << "Which file would you like to sort?\n";
    std::cin >> file;

    std::ifstream in(file.c_str());

    // Read all the ints from in:
    std::copy(std::istream_iterator<int>(in), std::istream_iterator<int>(),
            std::back_inserter(numbers));

    CountingSort(numbers);

    // Print the vector with tab separators:
    std::copy(numbers.begin(), numbers.end(),
            std::ostream_iterator<int>(std::cout, "\t"));
    std::cout << std::endl;

    return 0;
}

struct CalcMaxInt
{
    int maxInt;
    CalcMaxInt () : maxInt(0) {}
    void operator () (int i) { if (i > maxInt) maxInt = i; }
};

void CountingSort(vector<int>& numbers)
{
    CalcMaxInt cmi = std::for_each(numbers.begin(), numbers.end(), CalcMaxInt());
    //int maxInt = cmi.maxInt + 1;
    int maxInt = 130001;

    vector <int> temp1(maxInt);
    vector <int> temp2(maxInt);

    for (int i = 0; i < numbers.size(); i++)
    {
        temp2[numbers[i]] = temp2[numbers[i]] + 1;
    }

    for (int i = 1; i <= maxInt; i++)
    {
        temp2[i] = temp2[i] + temp2[i - 1];
    }

    for (int i = numbers.size() - 1; i >= 0; i--)
    {
        temp1[temp2[numbers[i]] - 1] = numbers[i];
        temp2[numbers[i]] = temp2[numbers[i]] -1;
    }

    for (int i =0;i<numbers.size();i++)
    {
        numbers[i]=temp1[i];
    }
    return;
}

score 2 · Accepted Answer

適切な範囲外の要素にアクセスしようとしています。temp2 の範囲は [0...maxInt-1] ですが、次のコードでは範囲外の temp2[maxInt] を使用しています。

for (int i = 1; i <= maxInt; i++)
{
    temp2[i] = temp2[i] + temp2[i - 1];
}

エラーが表示されないようにするには、temp2 を修正して maxInt+1 要素または i < maxInt にする必要があります。

score 1 · Accepted Answer

あなたがこれを行うことの要点ではありません：

 CalcMaxInt cmi = std::for_each(numbers.begin(), numbers.end(), CalcMaxInt());

最大要素を取得するには?

コードを次のように変更します。

void CountingSort(vector<int>& numbers)  
{  
    CalcMaxInt cmi;
    std::for_each(numbers.begin(), numbers.end(), cmi);          
    int maxInt = cmi.maxInt;

    vector <int> temp1(maxInt);    
    vector <int> temp2(maxInt);  

    // then the rest the same starting with the for loops
    // but with the fix that @kcm1700 mentioned to the for loop
}

score 0 · Accepted Answer

0

temp1寸法を記入してはいけませんnumbers.size()+1か?

于 2012-06-18T02:27:01.517 に答える

c++ - カウントソート無限ループ

3 に答える 3

Related

Reference