挿入とバブルソートの平均的な複雑さの分析

このサイトはすでにこのトピックに関するいくつかの質問がありますが、回答の一部を読んだ後は混乱します。上記のリンクで挿入とバブルソートの平均的な複雑さの分析

、「ジョー」によって答えは、平均してバブルソートにおけるスワップの数（n）は（N-1）/ 4である平均反転回数と同じであることを述べています。

Insertion sort vs Bubble Sort Algorithmsしかし、バブルソートの平均スワップ数はn^2/2であり、挿入ソートではn^2/4であり、それがバブルソートよりも挿入のソートの理由です。

どちらが正しいですか？誰か助けてくれますか？

2017-11-26 Zephyr

各ソースは平均ケースをどのように定義しますか？これらの比較はオレンジにリンゴかもしれません。最悪の場合と最悪の場合は、少なくとも不可解です。「平均」は分布を前提としています。 – Patrick87

@ Patrick87第2リンクはどうですか？それは平均的な挿入ソートがバブルソートに勝つと言います。また、答えは多くのupvotesを持っています。それが正しいか？ – Zephyr

これらの平均スワップ数はお互いに同じ範囲内にあります。マージソートやクイックソートのような分割征服のアプローチよりも、これら2つのソート方法を使用する必要がある理由がありますか？ –

あなたの最初のリンクは、均等な分布を仮定して、予想される逆転（すなわちスワップ）の数を数えます。

あなたの2番目のリンクは反復、つまり要素の検査です。

どちらも正しいです。

2017-11-29 04:09:09 wookie919

答えて