1

オンラインで疑似コードを見ずに独自のバブル ソート アルゴリズムを実装しようとしていましたが、成功したので、私のコードはオンラインで見た例とは大きく異なります。それらはすべて、真または偽のスワップされた変数の処理を伴います。私の実装にはそれがまったく含まれていないので、バブルソートを作成しませんでしたか?

これは私がオンラインで見た例です：

for i = 1:n,
swapped = false
for j = n:i+1, 
    if a[j] < a[j-1], 
        swap a[j,j-1]
        swapped = true
→ invariant: a[1..i] in final position
break if not swapped

終わり

これが私の実装です：

void BubbleSort(int* a, int size)
{
    while (!arraySorted(a, size))
    {
        int i = 0;
        while (i < (size-1))
        {
            if (a[i] < a[i+1])
            {
                i++;
            }
            else
            {
                int tmp = 0;
                tmp = a[i+1];
                a[i+1] = a[i];
                a[i] = tmp;
                i++; 
            }
        }
    }
}

働きは同じですが、何か違うのでしょうか？

4

1 に答える 1

0

一部の人が指摘したように、フラグのないバージョンは機能しますが、不必要に遅くなります。

ただし、元のバージョンを使用してフラグを ( と一緒にbreak) 破棄しても、引き続き機能します。便利に投稿した不変条件から簡単に確認できます。

ブレークのないバージョンは、ブレークがある場合とほぼ同じ最悪の場合のパフォーマンスを持ちます (最悪の場合は、逆順で並べ替えられた配列の場合です)。事前定義された時間内に終了することが保証されているアルゴリズムが必要な場合は、元のアルゴリズムよりも優れています。

ウィキペディアでは、バブル ソートの最適化の別のアイデアbreakについて説明しています。

于 2013-11-07T08:12:35.113 に答える