5

新しい質問を始めます。私は昨日質問をしましたが、私のプログラムで何が問題なのか知りたいと思っていました。プログラムを以下に示しますが、この次のプログラムはソートのパスを 1 つしか実行せず、外側のループも必要であると指摘されました。その時、私はOKのように良かったです。しかし、もう一度プログラムを見たときに混乱し、並べ替えを実行できるのは単一のループのみであるため、並べ替えに外部ループも必要な理由を尋ねる必要があります(私の意見では)。最初に以下のプログラムを参照してから、プログラムの最後にロジックを示します。

#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 < 9; 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<9;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

4 に答える 4

14

例を挙げましょう。3 つの数字だけを取ります。だからあなたは入力します

13, 3 ,1

今、あなたはそれをどのように行ったかを分類し始めます。13 と 3 を比較する 13 > 3ので、両方を切り替えます。今、私たちは持っています。

3, 13, 1

あなたが言ったように、次のペア= 13と1を比較すると 13 > 1、新しい順序は次のようになります

3, 1, 13

これでループが終了し、3 と 1 を比較するのに失敗しました。実際には、最初のループは最大数のみを並べ替えます。

于 2012-09-04T08:40:55.340 に答える
11

単一のループのみがソートを実行できるため（私の意見では）

これは正しくありません。詳細を説明しないと、並べ替えには問題があるため、一定数のループでは並べ替えに十分ではありません。Omega(nlogn)つまり、O(1)（1を含む一定の）ループ数では十分ではありません-どのアルゴリズムでも1,2。

入力を考慮する

5, 4, 3, 2, 1

バブルソートの単一ループで実行できます。

4, 5, 3, 2, 1
4, 3, 5, 2, 1 
4, 3, 2, 5, 1
4, 3, 2, 1, 5

したがって、アルゴリズムは、[ 4, 3, 2, 1, 5]ソートされていない array: になります。

バブル ソートを 1 回ループした後は、最後の要素が配置されていることが保証されます(この例では実際に発生しています)。2 回目の反復では、最後の 2 つの要素が配置されていることを確認し、2n回目の反復では、配列が実際に並べ替えられていることを確認します。その結果n、ネストされたループによってループが発生します。

(1) 外側のループは再帰呼び出しとして隠されることがあります (クイックソートはそれが起こる例です) - しかし、まだループがあります。
(2)正確には比較ベースのアルゴリズム。

于 2012-09-04T08:39:22.453 に答える
2

バブルソートの場合、パスは単純に最大の要素を配列の最後に移動します。したがって、ソートされた配列を取得するにはn-1回のパスが必要です。そのため、他のループが必要です。コード 1 パスの意味

if(number[0]>number[0+1])
{
    temp=number[0+1];
    number[0+1]=number[0];
    number[0]=temp;

}
if(number[1]>number[1+1])
{
    temp=number[1+1];
    number[1+1]=number[1];
    number[1]=temp;

}
.....6 more times
if(number[8]>number[8+1])
{
    temp=number[8+1];
    number[8+1]=number[8];
    number[8]=temp;

}

あなたが見ることができるように、IFステートメントが繰り返されているのを見ることができます.9つのIFすべての後、最大の要素が配列の最後に移動します

于 2012-09-04T08:40:53.170 に答える
1

これは正しくありません。

このアルゴリズムの名前は、小さい要素がリストの一番上に「バブル」する方法から付けられています。（バブルソート）

したがって、最初のループの終わりに、最小の要素を取得します。したがって、完全にソートするには、合計n個のループを保持する必要があります。（ここで、n =数値の合計サイズ）

于 2012-09-04T09:00:11.637 に答える