試験の改訂を行っています。
O（N ^ 2）の同じ平均的なケースの複雑さを考えると、どのような条件下で挿入ソートがバブルソートよりも優れたパフォーマンスを発揮するかを知りたい。
関連記事をいくつか見つけましたが、理解できません。
簡単な方法で説明してもらえますか？
24886 次
5 に答える
5
バブルソートの利点は、すでにソートされたリストを検出する速度にあります。
BubbleSort のベスト ケース シナリオ: O(n)
ただし、この場合でも、挿入ソートは改善されました/同じパフォーマンスが得られました。
バブルソートは、多かれ少なかれ、ソートアルゴリズムのメカニズムを理解したり教えたりするのに適していますが、最近のプログラミングでは適切な使用法を見つけることができません。その複雑さのためです
O(n²)
要素の数が少ないリストでは、その効率が劇的に低下することを意味します。
于 2012-05-03T09:40:57.747 に答える
4
次のことが頭に浮かびました。
バブル ソートでは、配列がソートされているかどうかを判断するために、常に配列をもう 1 回パスします。一方、挿入ソートはこれを必要としません。最後の要素が挿入されると、アルゴリズムは配列がソートされることを保証します。
バブル ソートは
n、すべてのパスで比較を行います。挿入ソートはn比較よりも少ないことを行います。アルゴリズムが現在の要素を挿入する位置を見つけると、比較を停止し、次の要素を取得します。最後に、ウィキペディアの記事から引用します。
バブル ソートは、最新の CPU ハードウェアとの相互作用も不十分です。少なくとも挿入ソートの 2 倍の書き込み、2 倍のキャッシュ ミス、漸近的に多くの分岐予測ミスが必要です。Java で文字列をソートする Astrachan による実験では、バブル ソートは挿入ソートよりも約 5 倍遅く、選択ソートよりも 40% 遅いことが示されています。
元の研究論文へのリンクがあります。
于 2012-05-03T10:16:52.220 に答える
0
私はあなたが探している答えはここにあると思います：
バブルソートは、非常に少数の要素を除いて、すでにソートされているリストでも効率的に使用できます。たとえば、1つの要素だけが順番に並んでいない場合、バブルソートには2n時間しかかかりません。2つの要素が順番に並んでいない場合、バブルソートにかかる時間は最大で3nです...
と
挿入ソートは、小さなリストやほとんどがソートされたリストに対して比較的効率的な単純なソートアルゴリズムであり、より高度なアルゴリズムの一部としてよく使用されます。
于 2012-05-03T09:30:47.767 に答える
0
理解できない関連記事へのリンクを提供していただけますか? 彼らがどのような側面に取り組んでいるのかはわかりません。それ以外に、バブル ソートは (リンク リストとして表されるものよりも) 配列として表されるコレクションに適しているのに対し、挿入ソートはリンク リストに適しているという理論的な違いがあります。
その理由は、バブル ソートは常に一度に 2 つの項目を交換することであり、これは配列とリンク リストの両方で自明です (配列ではより効率的です)。一方、挿入ソートは、特定のリスト内の場所に挿入します。これは、リンク リストでは自明ですが、配列内の後続のすべての要素を右に移動します。
そうは言っても、一粒の塩でそれを取ってください。まず第一に、配列のソートは、実際には、ほとんどの場合、リンクされたリストのソートよりも高速です。リストを一度スキャンすると、すでに大きな違いがあるという事実が原因です。それとは別に、配列の n 個の要素を右に移動することは、n 個 (または n/2 個) のスワップを実行するよりもはるかに高速です。これが、他の回答が挿入ソートが一般的に優れていると正しく主張している理由であり、あなたが読んだ記事について私が本当に疑問に思っている理由です。 B.
于 2012-05-03T10:17:55.313 に答える