99

いくつかのソート アルゴリズムを理解しようとしていますが、バブル ソートと挿入ソート アルゴリズムの違いを理解するのに苦労しています。

どちらも O(n 2 ) であることはわかっていますが、バブル ソートはパスごとに配列の最大値を一番上にバブルするだけで、挿入ソートはパスごとに最小値を一番下に沈めるように思えます。まったく同じことをしているのに、方向性が違うのではありませんか?

挿入ソートの場合、比較/潜在的なスワップの数はゼロから始まり、毎回増加します (つまり、0、1、2、3、4、...、n) が、バブル ソートの場合、これと同じ動作が発生します。並べ替え (つまり、n、n-1、n-2、... 0)。これは、バブル 並べ替えが、並べ替えられた最後の要素と比較する必要がなくなるためです。

ただし、これらすべてについて、一般的に挿入ソートの方が優れているというコンセンサスがあるようです。誰でも理由を教えてもらえますか?

編集:私は主にアルゴリズムの動作の違いに興味があり、効率や漸近的な複雑さにはあまり興味がありません。

4

12 に答える 12

137

挿入ソート

i回の反復の後、最初のi個の要素が順序付けられます。

各反復では、次の要素が正しい場所に到達するまでソートされたセクションを通過します。

sorted  | unsorted
1 3 5 8 | 4 6 7 9 2
1 3 4 5 8 | 6 7 9 2

4 はソートされたセクションにバブリングされます

擬似コード:

for i in 1 to n
    for j in i downto 2
        if array[j - 1] > array[j]
            swap(array[j - 1], array[j])
        else
            break

バブルソート

i回の反復の後、最後のi要素が最大であり、順序付けられています。

各反復で、ソートされていないセクションをふるいにかけ、最大値を見つけます。

unsorted  | biggest
3 1 5 4 2 | 6 7 8 9
1 3 4 2 | 5 6 7 8 9

5 は、ソートされていないセクションから吹き出されます

擬似コード:

for i in 1 to n
    for j in 1 to n - i
         if array[j] > array[j + 1]
             swap(array[j], array[j + 1])

典型的な実装は、外側のループの繰り返しの 1 つの間にスワップが行われない場合、早期に終了することに注意してください (配列がソートされることを意味するため)。

違い

挿入ソートでは要素がソートされたセクションにバブリングされますが、バブルソートでは最大値がソートされていないセクションからバブリングされます。

于 2013-06-24T09:15:27.030 に答える
46

i 回目の反復のバブル ソートでは、合計で ni-1 回の内部反復 (n^2)/2 がありますが、挿入ソートでは、i 番目のステップで最大 i 回の反復がありますが、内部ループを停止できるため、平均で i/2 です。以前、現在の要素の正しい位置を見つけた後。したがって、(0 から n までの合計) / 2 は (n^2) / 4 の合計になります。

そのため、挿入ソートはバブル ソートよりも高速です。

于 2013-06-24T08:20:16.687 に答える
8

バブル ソートは、ソートされた要素のグローバルな最大値を実際に追跡しないため、オンラインではありません (アイテムの数を知らずに入力ストリームをソートすることはできません)。アイテムが挿入されたら、最初からバブリングを開始する必要があります

于 2014-08-09T15:28:27.760 に答える
5

バブルソートは、誰かが多数のリストから上位k個の要素を探している場合にのみ、挿入ソートよりも優れています。つまり、k回の反復後にバブルソートで上位k個の要素が取得されます。ただし、挿入ソートで k 回反復した後は、それらの k 要素がソートされることのみが保証されます。

于 2014-06-26T10:54:11.997 に答える
2

両方の並べ替えは O(N^2) ですが、隠し定数は挿入並べ替えではるかに小さくなります。隠し定数は、実行されたプリミティブ操作の実際の数を参照します。

挿入ソートの実行時間が改善されるのはいつですか?

  1. 配列はほぼソート済みです。この場合、挿入ソートはバブル ソートよりも操作が少ないことに注意してください。
  2. 配列は比較的小さいサイズです: 現在の要素を配置するために要素を移動する挿入ソート.これは、要素の数が少ない場合にのみバブルソートよりも優れています.

挿入ソートが常にバブル ソートよりも優れているとは限らないことに注意してください。両方の世界を最大限に活用するには、配列のサイズが小さい場合は挿入ソートを使用し、大きな配列の場合はマージ ソート (またはクイックソート) を使用します。

于 2013-06-24T08:25:03.680 に答える
0

バブル ソートは、すべての状況でほとんど役に立ちません。挿入ソートのスワップが多すぎる可能性があるユースケースでは、N 回未満のスワップが保証されるため、選択ソートを使用できます。選択ソートはバブル ソートよりも優れているため、バブル ソートにはユース ケースがありません。

于 2016-07-26T05:28:41.123 に答える
-1

挿入ソートは次のように再開できます。最初の位置 (最小) にある要素を探し、次の要素をシフトしてスペースを空けて最初の位置に配置します。 ...」など...

バブル ソートの動作は異なりますが、「順序が間違っている隣接する 2 つの要素を見つけたら、それらを入れ替えます」として再開できます。

于 2013-06-24T08:32:47.317 に答える