[解決済み] 挿入ソートとバブルソートアルゴリズムの比較

質問

いくつかのソートアルゴリズムを理解しようとしているのですが、バブルソートと挿入ソートのアルゴリズムの違いがわからず、悩んでいます。

どちらもO(n ² )ですが、バブルソートは各パスで配列の最大値を先頭に泡立てるだけで、挿入ソートは各パスで最小値を底に沈めるだけのような気がするのですが。これらはまったく同じことをやっていますが、方向が違うのではありませんか？

挿入ソートでは、比較/ポテンシャルスワップの数はゼロから始まり、毎回増加します（つまり、0、1、2、3、4、...、n）。しかしバブルソートでは、この同じ動作が起こりますが、ソートの終わりには（つまり、n、n-1、n-2、... 0）、バブルソートはもはや最後の要素との比較が不要になるためソートが行われるため、このようになります。

しかし、このすべてについて、挿入ソートが一般的に優れているというコンセンサスがあるようです。なぜなのか、誰か教えていただけませんか？

編集 私は主に、効率や漸近的な複雑さではなく、アルゴリズムがどのように動作するかの違いに興味があります。

どのように解決するのですか?

バブルソートでは、最初の反復でn-i-1回の内部反復を行います。つまり、(0からnまでの合計) / 2で、合計(n^2) / 4となります。

これが挿入ソートがバブルソートより高速な理由です。