0

挿入ソートはバブルソートよりも速い選択ソートよりも高速であり、3つすべての実行時間はO（n ^ 2）であると書き留めましたが、それらを比較するにはどうすればよいですか？

4

3 に答える 3

7

並べ替えアルゴリズムを次の基準と比較できます。

  1. 時間計算量（Big-O表記）。ベストケース、ワーストケース、および平均実行時間は、時間の複雑さが異なる可能性があることに注意してください。たとえば、バブルソートのベストケースはO（n）のみであり、元のリストがほぼ順番に並んでいる場合（多くの要素がずれていない場合）、選択ソートよりも高速になります。
  2. メモリの複雑さ。nが大きくなるにつれて、リストをソートするために必要なメモリはどれくらいですか？
  3. 安定。並べ替えは、同等の並べ替え値を持つ要素の相対的な順序を保持しますか？（たとえば、カタログアイテムのリストを価格で並べ替えている場合、一部の要素の価格が同じである可能性があります。カタログが元々アイテム名でアルファベット順に並べ替えられていた場合、選択した並べ替えアルゴリズムは、同じ価格の各グループ内でアルファベット順を保持しますか？アイテム。）
  4. 必要な比較のベスト/ワースト/アベレージ数。比較操作に費用がかかる場合に重要です。（例：シミュレーションまたはその他の複雑な計算によって効率が計算される代替設計の効率の比較）。
  5. 必要なスワップ操作のベスト/ワースト/平均数。スワップ操作に費用がかかる場合に重要です。（例：船の甲板上で物理的に移動する必要がある輸送コンテナの分類）
  6. コードサイズ。バブルソートは、コードのフットプリントが小さいことで知られています。
于 2012-10-15T00:18:06.080 に答える
1

挿入/選択/バブルソートがすべてn^2時間で実行されることを確認する方法はいくつかあります。

  • それらはネストされたループを使用します：n個の外部ループ、およびそれぞれが平均してn/2個の内部ループを持ちます
  • それらは要素のすべてのペアを比較します：n *（n-1）/2ペアがあります

挿入/選択/バブルソートの実行に関する詳細な分析を次に示します。

于 2013-12-06T09:47:38.423 に答える
0

バブルソートの利点は、すでにソートされているリストを検出する速度にあります。

バブルソートのベストケースシナリオ：O（n）

ただし、この場合でも、挿入ソートのパフォーマンスは向上/同じになりました。

バブルソートは、多かれ少なかれ、ソートアルゴリズムのメカニズムを理解および/または教えるためだけに適していますが、その複雑さのために、最近のプログラミングでは適切な使用法を見つけることができません

O（n²）

少数以上の要素のリストでは、その効率が劇的に低下することを意味します。

于 2020-06-10T23:01:10.250 に答える