私はいくつかのソートアルゴリズムを理解しようとしていますが、バブルソートと挿入ソートのアルゴリズムの違いを理解するのに苦労しています'。
どちらもO(n2)ですが、バブルソートは各パスで配列の最大値を上にバブルさせるだけ、挿入ソートは各パスで最小値を下に沈めるだけのような気がするのですが。両者は全く同じことをやっているのですが、方向性が違うのではないでしょうか?
挿入ソートでは、比較/ポテンシャルスワップの数はゼロから始まり、毎回(つまり0、1、2、3、4、...、n)増加しますが、バブルソートではこれと同じ動作が起こりますが、ソートの最後に(つまりn、n-1、n-2、...、0)バブルソートはもはやソートの際に最後の要素と比較する必要がないためです。
しかし、一般的には挿入ソートの方が良いというのがコンセンサスになっているようです。その理由を教えてください。
編集部:「私は、効率や漸近的な複雑さよりも、アルゴリズムの仕組みの違いに興味があるんです」。
各反復で、次の要素は、 sorted セクションを通って適切な場所に到達するまでバブリングされます。
sorted | unsorted
1 3 5 8 | 4 6 7 9 2
1 3 4 5 8 | 6 7 9 2
疑似コード:
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
各反復で、分類されていないセクションをふるいにかけて、最大値を見つけます。
unsorted | biggest
3 1 5 4 2 | 6 7 8 9
1 3 4 2 | 5 6 7 8 9
疑似コード:
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つ中にスワップが行われない場合、典型的な実装は早期に終了することに注意してください(これは、配列がソートされることを意味します)。
挿入では、ソート要素はソートされたセクションにバブルされますが、バブルのソートでは、最大値がソートされていないセクションからバブルされます。
別の違い、私はここで見ませんでした:
バブルソートには、スワップごとに 3の値割り当てがあります: 最初にプッシュしたい値(no.1)を保存するには一時変数を作成する必要があります。次に、他のスワップ変数(no.2)を保存したばかりのスポットに書き込み、次に一時変数を他のスポット(3番)に書き込む必要があります。 変数を正しいスポットにソートするには、スポットごとにそれを行う必要があります。
挿入ソートを使用すると、変数を一時変数にソートして、変数の正しいスポットに到達する限り、すべての変数をそのスポット1スポットの前に後方に配置します。 これにより、スポットごとに 1値の割り当てになります。 最後に、一時変数をその場所に書き込みます。
これにより、価値の割り当てもはるかに少なくなります。
これは最も強力なスピードベネフィットではありませんが、言及できると思います。
私は理解できると思います。理解できなくても、申し訳ありませんが、私は英国ではありません。
挿入ソートの主な利点は、オンラインアルゴリズムであることです。 開始時にすべての値を持つ必要はありません。 これは、ネットワークまたは一部のセンサーからのデータを処理するときに役立ちます。
これは他の従来の「n log(n)」アルゴリズムよりも高速だと感じています。 複雑さは n *(n log(n))
になるためです。 ストリームから各値を読み取って保存し( O(n)
)、次にすべての値( O(n log(n))
)をソートすると、O(n ^ 2 log(n))
になります。
逆に、[並べ替えの挿入]を使用すると、ストリームから値を読み取るには O(n)
が必要で、値を正しい場所に配置するには O(n)
が必要です。したがって、 O(n ^ 2)
のみです。 その他の利点は、値を格納するためのバッファーを必要とせず、最終目的地でそれらを並べ替えることです。
-挿入ソートは、各反復で最大1回のスワップを行います。 -バブルソートは、各反復で0〜nスワップを行います。
-挿入ソートは、ソートされたパーツにアクセス(および必要に応じて変更)して、考慮されている数値の正しい位置を見つけます。 -最適化すると、Bubble-sortはすでにソートされているものにアクセスできなくなります。
-挿入ソートはオンラインです。 つまり、挿入ソートは、適切な位置に配置する前に、一度に1つの入力を取ります。 「隣接入力」のみを比較する必要はありません。 -バブルソートはオンラインではありません。 一度に1つの入力を操作しません。 各反復で入力のグループ(すべてではないにしても)を処理します。 バブルソート各反復で「隣接入力」**のみを比較して交換します。