6

コードに問題がないか何度もチェックしましたが、バブルソートプログラムが正しい出力を提供しない理由を理解できません。識別を手伝ってもらえますか？

#include <iostream.h>
#include <conio.h>

 using namespace std;

 main()

{
  int number[10];
  int temp=0;
  int i=0;

  cout<<"Please enter any ten numbers to sort one by one: "<<"\n";

  for (i=0;i<10;i++)
  {
      cin>>number[i];
      }
  i=0;

  for (i=0;i<10;i++)
  {

      if(number[i]>number[i+1])

      {
      temp=number[i+1];
      number[i+1]=number[i];
      number[i]=temp;
                          }

      }
      i=0;
      cout<<"The sorted numbers are given below:"<<"\n";

      for (i=0;i<10;i++)
      {
        cout<<number[i]<<"\n";  
          }

          getch();
  }

編集：私はあなた方全員が外側のループがなければならないと言ったことを受け入れました。しかし、もう一度私は自分が書いたものについて考えています。バブル状態の唯一のループがソートを行うべきだと思います。これが私が考えていることです：

for (i=0;i<10;i++)
    if(number[i]>number[i+1])
    {
        temp=number[i+1];
        number[i+1]=number[i];
        number[i]=temp;

    }
}

ここで、このループが「すべき」ことを私が考えていることを説明します。まず、number[0]とnumber[1]を比較します。条件が満たされると、IFステートメントの本文にあることを実行します。次に、iが1（i ++）ずつインクリメントされます。次に、次の反復で、比較される値はnumber[1]とnumber[2]になります。では、なぜそれが起こらず、パスしただけでループが終了するのでしょうか。言い換えれば、私はIFステートメントがforループで繰り返されないようにしようとしているのでしょうか？私の意見ではそうです。私は助けと意見にとても感謝しています。私の質問は小さなレベルかもしれませんが、それが私がどのように進歩するかです。ありがとう。

4

6 に答える 6

3

これは、バブル ソートの最初のパスにすぎません。パス中に並べ替えが実行されなくなるまで、並べ替え部分を繰り返す必要があります。

于 2012-09-03T11:25:34.267 に答える
2
  • バブル ループは 1 回だけ実行します。すべてが並べ替えられるまで実行する必要があります。
  • バブル ループが 10 になり、 にアクセスしますnumber[i+1]。これは未定義の動作です

メインループを修正する方法は次のとおりです。

bool again;
do {
    again = false;
    for (i=0;i<9;i++)
    { //       ^-- Nine, not ten
        if(number[i]>number[i+1])
        {
            temp=number[i+1];
            number[i+1]=number[i];
            number[i]=temp;
            again = true;
        }
    }
} while (again);
于 2012-09-03T11:25:33.400 に答える
1

バブル ソートは O(n*n) (最悪の場合) ----> 反復から終了までの内部ループが必要です。次に、O(nlogn) や O(n) などのより良い状況を得るために、途中で終了したかどうかを確認する必要があります。

for (i=0;i<9;i++)     //from 0 up to N-1
{ 
  failed=false;      //for the checking if finished
  for(int j=i+1;j<10) //from next element up to N
   {
     if(number[i]>number[j])
     {
         temp=number[j];
         number[j]=number[i];
         number[i]=temp;
         failed=true;
      }


   }
  if(!failed)break;         //if failed=false then it is done.
}

あなたのエラーは0から1回だけ繰り返されていました---> N

  • 次の要素が最終的に N になるため、外側のループは 0--->N-1 から進む必要があります。
  • 内側のループは i+1 から N に移動する必要があります。i+1 はnext要素を表します。

n*n 回の繰り返しの前に完了したときに中断する必要がある場合は、ブール値で通知する必要があります

例：

Initial : 4 9 3 6 2 5 7

1st pass: 4 3 6 2 5 7 9  ---> failed at many i(you see "9" bubbled )

2nd pass: 3 4 2 5 6 7 9 ---> failed at several i's(you see "6" bubbled)

3rd pass: 3 2 4 5 6 7 9 ---> failed(once) at 4 and 2(you see "4" bubbled)

4th pass: 2 3 4 5 6 7 9 ---> failed once at 2 and 3(3 bubbles)

5th pass: 2 3 4 5 6 7 9 --->same! did not fail. Finished without looping 2  more
于 2012-09-03T11:25:47.253 に答える
1

持っているとかなり危険

int number[5];

ユーザーに10個の値を入力するように依頼します;-)

于 2012-09-03T11:26:02.503 に答える
1

配列の範囲を超えています。ループを 10 回ではなく 5 回実行します。

次に、1 回のパスで配列をソートしようとしています。ネストされたループを作成します。完全なソート用。たとえば、この配列がある場合。

3  4  1  2  6

あなたがやっているように、1回のパスの後、それはこのようになります。

3  1  2  4  6

したがって、この配列は完全にはソートされていません。完全な並べ替えのために 2 つのループを作成します。

そして、必ずループを実行してくださいsize - 1

于 2012-09-03T11:26:03.930 に答える
0

サイズ 5 の配列を宣言しているが、number[5]10 個の要素を入力してアクセスしようとしているために発生している可能性があります。

配列に10個の要素を入れたい場合は、次のように宣言しますint number[10];

for ループを次のように使用します。

for (i=0;i<9;i++)     //from 0 up to N-1
{
  for(int j=i+1;j<10) //from next element up to N
   {
  if(number[i]>number[i+1])

     {
  temp=number[i+1];
  number[i+1]=number[i];
  number[i]=temp;
      }

   }
}
于 2012-09-03T11:27:35.517 に答える