1

私はソートを学んでいます（初めてではありません）。バブルソートでは、コードとして以下を持っています。

int bubble_sort(int *arr, size_t n) {

    size_t i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }

    return 0;
}

ご覧のとおり、内側のループにはn-1(for ループ内で) 時間があり、これは理解できます (a[i],a[i-1]どちらも 1 回の反復に含まれます)。ただし、外側のループには がありますがi < n、i < n-1しかし、インターネットでのほとんどの実装には n、外側のループ値があります。外側のループを実行n-1すると、最悪の場合でも問題なく動作し5 4 3 2 1ます。n-1外部ループの時間で機能しない入力のセットがあるかどうか疑問に思っています。ある場合は、投稿して説明してください。ありがとう。

4

2 に答える 2

3

N-1でも大丈夫です。あなたが説明したように、最悪のケースでは N-1 スワップが必要です (最後が最初になる必要があり、その逆も同様です)。i 変数の出力を if ステートメントの内部に追加すると、最後の反復で呼び出されないことがわかります。これは、ループの最後の繰り返しでスワッピングが発生しないことを意味します。

ただし、Bubblesort のさらに効率的な実装では、for ループを外側のループとして使用しません。以下のコードを見てください。実行の違いがわかりますか?

int bubble_sort(int *arr, size_t n) {
    size_t i,j;
    int flag = 1;
    while (flag) {
        flag = 0;
        for(j=0;j<n-1;j++) {
            if(arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                flag = 1;
            }
        }
    }
    return 0;
}

実際のスワッピングが発生した場合にのみフラグを設定することで、平均的なケースでは、はるかに早くループから飛び出すことになります。

于 2012-10-09T17:43:47.700 に答える
1

いいえ、そのような入力はありません。

理論的根拠は、バブルソートの証明にあります。iバブルソートの（外側の）反復でそれを証明するとき、i最後の要素が配置され、ソートされていることを思い出してください。

したがって、n-1反復後、最後のn-1要素が配置されて並べ替えられ、残りの最初の要素のみが残ります。これは、正しい場所、つまり配列の最初の場所にのみ配置できます。

（したがって、このアプローチを使用すると、バブルソートには最大で外部反復が必要であることを証明できます）n-1

また、注意：従来のバブルソートn-iでは、内側のループでの反復のみが必要であり（前述の有理数のため）、必要ありませんn-1。

于 2012-10-09T17:49:22.923 に答える