3

私はプログラミングの初心者で、並べ替えで遊んでいて、このアルゴリズムを作成しました。バブルに似ていますが、隣接するペアではなく、1 番目と 2 番目、1 番目と 3 番目、2 番目と 3 番目、2 番目と 4 番目などのペアを比較します。アルゴリズムのパフォーマンス/効率を教えてください。またはバブルと比較してください。または、少なくとも問題を自分で解決する方法についてアドバイスしてください。これよりどれくらいの泡がいいのか興味があります。ありがとうございました。

void sortArray(int a[]) {

int q, x, temp;

for ( q = 0; q < SIZE - 1; q++ ) {
    for ( x = q + 1; x < SIZE; x++ ) {
        if (a[q] < a[x]) {
            temp = a[q];
            a[q] = a[x];
            a[x] = temp;
        }
    }
}

}

4

3 に答える 3

2

あなたのソートは古典的なバブルソートに似ており、本質的に同じパフォーマンスを持つはずです。

ソートとバブル ソートはどちらも、選択ソートの非効率的なバージョンと見なすことができます。3 つのアルゴリズムすべてで、内側のループの各パスは、配列の並べ替えられていない領域を反復処理し、最小/最大の要素を見つけて、最終的な場所に残します。アルゴリズムは、ソートされていない領域で異なる順列を実行するため、同一ではありませんが、この違いはアルゴリズムの動作に機能的に寄与しません。

これを認識すれば、選択ソートが他の 2 つよりも定数係数の利点を持つ傾向がある理由を簡単に理解できます。内部ループの各パスは、必要な最小数のスワップ (つまり、最後に 1 つ) を実行します。対照的に、バブルソートとあなたのソートは、内側のループの繰り返しごとに1回のスワップを行うことになるかもしれません...

ただし、漸近的には、3 つの並べ替えすべてに O(N^2) 時間がかかります。具体的にN*(N-1)/2は、内側のループの反復があります。

于 2013-03-27T19:08:33.940 に答える
1

簡単な答え - あなたのアルゴリズムの複雑さは O(n 2 ) です - ちょうどバブル ソートと同じです。つまり、両方のアルゴリズムの複雑さは本質的に同じです。

于 2013-03-27T19:13:54.480 に答える
0

@Kevin は、外側のループの n 回目の反復で最初の n 個の要素が正しい位置にあると言ったときに正しいです。従来のバブル ソート (隣接する要素の比較と交換) もこれを行いますが、リスト内の他の項目も部分的にソートされるため、すべての反復が完了する前にリストがソートされる可能性が高くなるという利点があります (ソートが終了する可能性のある外側のループ反復中にスワップは検出されません)。

于 2013-03-27T19:08:04.387 に答える