3

私は数年間プログラミングのクラスを行っていないので、初心者の間違い/何かをする方法を許してください. 未来への提案が欲しい。以下のコードでは、2 つの配列 (既にソート済み) の値をチェックし、それらを組み合わせた配列に入れようとしています。私の解決策は、非効率的/ずさんですが、for ループを使用して各配列の j のインデックスの内容を比較し、低い値を結合配列のインデックス i に割り当て、高い値をインデックス i+1 に割り当てます。前のループのインデックスを上書きしないように、i を 2 増やします。

int sortedArray1 [5] = {11, 33, 55, 77, 99};
int sortedArray2 [5] = {22, 44, 66, 88, 00};
combinedSize = 10;
int *combinedArray;
combinedArray = new int[combinedSize];
    for(int i = 0; i <= combinedSize; i+=2)
{
    for(int j = 0; j <= 5; j++)
    {
        if(sortedArray1[j] < sortedArray2[j])
        {
            combinedArray[i] = sortedArray1[j];
            combinedArray[i+1] = sortedArray2[j];
        }
        else if(sortedArray1[j] > sortedArray2[j])
        {
            combinedArray[i] = sortedArray2[j];
            combinedArray[i+1] = sortedArray1[j];
        }
        else if(sortedArray1[j] = sortedArray2[j])
        {
            combinedArray[i] = sortedArray1[j];
            combinedArray[i+1] = sortedArray2[j];
        }
    }
}

for(int i = 0; i < combinedSize; i++)
{
    cout << combinedArray[i];
    cout << " ";
}

そして私の結果はこれです

Sorted Array 1 contents: 11 33 55 77 99
Sorted Array 2 contents: 0 22 44 66 88
5 77 5 77 5 77 5 77 5 77 Press any key to continue . . .

経験の浅い私の考えでは、ソートの実装は良さそうに見えるので、なぜこの悪い出力が得られるのかわかりません。アドバイスは素晴らしいでしょう。

4

6 に答える 6

3

これはどうですか：

int i=0,j=0,k=0;
while(i<5 && j<5)
     {
        if(sortedArray1[i] < sortedArray2[j])
         {
           combinedArray[k]=sortedArray1[i];
            i++;
          }
       else
         {
           combinedArray[k]=sortedArray2[j];
           j++;
          }
      k++;
     }
   while(i<5)
     {
           combinedArray[k]=sortedArray1[i];
           i++;k++;
          }
   while(j<5)
     {
           combinedArray[k]=sortedArray2[j];
           j++;  k++;

          }
于 2012-09-23T04:10:54.590 に答える
3

まず、C++ の使用方法には差し迫った問題がいくつかあります。

  • =等値チェックの代わりに使用します==（したがって、望ましくない値の割り当てと、そうでない場合に if 条件が true を返す原因となります）。
  • 外側のループの上限は として定義されてi <= 10いますが、正しい境界チェックはi < 10;
  • メモリの割り当て解除に失敗したため、関数の最後にメモリ リークが発生しました。最後にが必要ですdelete [] combinedArray。

次に、外側のループが宛先配列のすべての値を反復し、各ステップで内側のループを使用してソース配列のすべての値を反復します。それはあなたが望むものではありません。必要なのは、から数えてソース配列を反復する1 つのループです。宛先配列内の位置は と として決定され、内部ループは必要ありません。j=0j<52*j2*j+1

3 番目に、コメントで説明されているように、ソートされたリストのマージを正しく実装するには、2 つの独立したカウンターj1とが必要j2です。ただし、現在の入力はコードに組み込まれており、 に置き換える00と100、現在のアルゴリズム (上記の修正が行われた後) が実際に指定された入力に対して機能します。

最後に、それほど重要ではありませんが、目的の配列が を使用してヒープに割り当てられているのはなぜでしょうかnew。小さな配列を扱っている限り、ソース配列と同じようにスタックに割り当てることができます。ただし、ヒープに割り当てる場合は、 をstd::unique_ptr<>組み合わせて使用​​することをお勧めしますstd::array<>。delete []関数の最後にステートメントを配置することを考える必要なく、無料で割り当てを解除できます。

于 2012-09-23T04:26:58.660 に答える
1

実装を見る前に、アルゴリズムをチェックして、ペンと紙で書き留めてください。最初に表示されるのは、結果の最初の 2 つの要素が各ソース配列から 1 つ取得されると想定していることです。そうである必要はありません。一方のすべての要素が他方のすべての要素よりも小さい 2 つの配列と、期待される結果を考えてみましょう。

int a[] = { 1, 2, 3 };
int b[] = { 4, 5, 6 };

結果を並べ替える場合、最初の 3 つの要素はすべて最初の配列から取得されます。それを念頭に置いて、データについて本当に知っていることを考えてください。特に、両方の配列がソートされます。つまり、最初の要素は、それぞれの配列の残りの要素よりも小さくなります。これは、要素が小さいほどヘッドが小さいことを意味します。その要素を結果に入れることで、問題をより小さなセットに減らしました。a' = { 2, 3 }、b = { 4, 5, 6 }および、およびソートされていることを知っているres = { 1 }ことの 2 番目の要素を見つけるという新しい問題があります。resa'b

何をする必要があるかを紙で把握し、それをコードにマッピングするのは簡単です。

于 2012-09-23T04:29:13.290 に答える
1

そのため、コードを修正して機能させました。実際には、2 つのソートされた配列に対して 2 つのポインター/インデックスを用意することをお勧めします。結合配列に追加した後、対応するポインターを更新できるようにします。このコードの一部が理解できない場合はお知らせください。ありがとう。

    int sortedArray1 [5] = {11, 33, 55, 77, 99};
    int sortedArray2 [5] = {0, 22, 44, 66, 88}; 
    int combinedSize = 10;
    int *combinedArray;
    combinedArray = new int[combinedSize];
    int j = 0;
    int k = 0;
    for(int i = 0; i < combinedSize; i++)
    {
            if (j < 5 && k < 5) {
                    if (sortedArray1[j] < sortedArray2[k]) {
                            combinedArray[i] = sortedArray1[j];
                            j++;
                    } else {                  
                            combinedArray[i] = sortedArray2[k];
                            k++;
                    }                         
            } 
            else if (j < 5) {
                    combinedArray[i] = sortedArray1[j];
                    j++;
            }                         
            else {
                    combinedArray[i] = sortedArray2[k];
                    k++;
            }                         
    }

    for(int i = 0; i < combinedSize; i++)
    {
        cout << combinedArray[i];
        cout << " ";
    }
    cout<<endl;
于 2012-09-23T07:30:56.890 に答える
0

のelse if(sortedArray1[j] = sortedArray2[j])、ということelse if(sortedArray1[j] == sortedArray2[j])ですか？

前者は、sortedArray2[j] の値を sortedArray1[j] に割り当てます。これが、取得する理由です。5 77 5 77...

しかし、5どこから来たのですか？どちらsortedArrayにも 5 はfor(int j = 0; j <= 5; j++)ありませんが、何か問題があるに違いありません。サイズN配列の最大インデックスは、C/C++ ではなく (Basic ではなく).. 条件として使用します。そうしないとN-1、説明や予測が難しい状況に陥る可能性があります..Nj<5

結局のところ、アルゴリズム自体に問題があります。外側のループがループするたびに、最後に 2 つの配列の最後の要素が比較され、出力が 2 つの数値を繰り返すことになります。

したがって、アルゴリズムも修正する必要があります。 Merge Sortを参照してください。

于 2012-09-23T04:08:17.340 に答える