1

カウントソート関数を作成しようとしていますが、何らかの理由で最初のforループ内でスタックしています。誰かが私のロジックの何が問題なのか教えてもらえますか？私はC++を初めて使用するので、学習できるように回答を説明してください。前もって感謝します！

maxInt編集： 130,000未満を入力した場合にのみ、問題（「CountSort.exeが動作を停止しました」というウィンドウポップアップ）が発生します。それよりも大きい数値を入力すると、うまく機能します。並べ替えたい番号のリストは、私が読んだ外部の.txtファイルからのものです。番号は次のとおりです。1462 34 65 2 3 64 2 12 97 56 45 3 43 23 99 2

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

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

    vector <int> temp1(maxInt);
    vector <int> temp2(maxInt);
    int min = 0;

  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;
}
4

1 に答える 1

4

アルゴリズムエラーは探していませんが、一時ベクトルのサイズを大きくして、初期化する必要があります0（これはパラノイア用であり、デフォルトの初期化子はですint）0。

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

それを修正した後、プログラムは私のシステムで実行されているようで、逆にソートされた配列を正しくソートします。ただし、より完全なテストケースのセットを使用してテストする必要があります。

ソートのカウント方法のため、maxIntパラメーターは、入力配列が保持する最大値より少なくとも1つ大きい値である必要があります。

関数を変更して、ベクトルをパスし、最大のものを見つけることができます。

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

CalcMaxInt cmi = std::for_each(numbers.begin(), numbers.end(), CalcMaxInt());
int maxInt = cmi.maxInt + 1;

そうすれば、それを渡す必要はありません。

入力用に読み込んだものを印刷するためのコードを追加して、それが本来あるべきものであると確信できるようにすることができます。

于 2012-06-13T00:44:59.630 に答える