いくつかのソート アルゴリズムを理解しようとしていますが、バブル ソートと挿入ソート アルゴリズムの違いを理解するのに苦労しています。
どちらも O(n 2 ) であることはわかっていますが、バブル ソートはパスごとに配列の最大値を一番上にバブルするだけで、挿入ソートはパスごとに最小値を一番下に沈めるように思えます。まったく同じことをしているのに、方向性が違うのではありませんか?
挿入ソートの場合、比較/潜在的なスワップの数はゼロから始まり、毎回増加します (つまり、0、1、2、3、4、...、n) が、バブル ソートの場合、これと同じ動作が発生します。並べ替え (つまり、n、n-1、n-2、... 0)。これは、バブル 並べ替えが、並べ替えられた最後の要素と比較する必要がなくなるためです。
ただし、これらすべてについて、一般的に挿入ソートの方が優れているというコンセンサスがあるようです。誰でも理由を教えてもらえますか?
編集:私は主にアルゴリズムの動作の違いに興味があり、効率や漸近的な複雑さにはあまり興味がありません。