algorithm - バブルソートは何に適していますか？

Question

バブルソートは実際に使用されますか? 言及されているのを見るたびに、それは常に次のいずれかです。

学習する並べ替えアルゴリズム。
使用しないソートアルゴリズムの例。

score 81 · Accepted Answer

バブルソートは、(おそらく)非常に特殊な状況下で利用できる最速のソートです。厳密に分析された (あらゆる種類の) 最初のアルゴリズムの 1 つであり、限られた状況下で最適であることが証明されたことが主な理由です。

テープドライブにファイルが格納されていて、ランダムアクセスメモリ (または非常に大きなキー) が非常に少ないため、一度に2 つのレコードしかメモリにロードできないとします。テープの巻き戻しは非常に遅いため、ファイル内でランダムアクセスを行うことは一般的に非現実的です。可能であれば、一度に 2 つまでのレコードを順番に処理する必要があります。

テープドライブが一般的で、数千 (ワード|バイト) の RAM (種類を問わず) しか搭載されていないマシンが一般的だった頃、それは十分に現実的であり、研究する価値がありました。そんな状況は今では珍しくなっているので、バブルソートを勉強してもあまり意味がありませんが、さらに悪いことに、最適な状況が教えられていないため、適切な状況が発生した場合でも、ほとんど誰もそれに気付きません。

非常に小さい、および/またはほぼソートされたデータセットで最速である限り、それはバブルソートの弱点を（少なくともある程度まで）カバーできますが、挿入ソートは本質的に常にどちらか/両方に適しています.それらの。

score 47 · Accepted Answer

それは、データの配布方法によって異なります-いくつかの仮定を立てることができるかどうか。

バブルソートまたはその他のソートをいつ使用するかを理解するために私が見つけた最良のリンクの1つは、これです-ソートアルゴリズムのアニメーションビュー:

http://www.sorting-algorithms.com/

score 20 · Accepted Answer

現実世界ではあまり使われません。理解しやすく、すぐに実装できるため、優れた学習ツールです。悪い (O(n^2)) 最悪のケースと平均的なパフォーマンスがあります。データがほぼソートされていることがわかっている場合は、最良の場合のパフォーマンスが優れていますが、このプロパティを持つ他のアルゴリズムはたくさんあり、最悪および平均の場合のパフォーマンスが向上しています。

score 10 · Accepted Answer

最近の最適化の逸話で、それの素晴らしい使い方に出くわしました。プログラムでは、フレームごとに深さ順にソートされた一連のスプライトが必要でした。悪意の順序はフレーム間であまり変わらないため、最適化として、フレームごとに 1 回のパスでバブルソートされました。これは、両方向 (上から下および下から上) で行われました。そのため、スプライトは常に非常に効率的な O(N) アルゴリズムでほぼソートされていました。

score 7 · Accepted Answer

おそらく、小さなセットでは最速です。

教育といえば。並べ替えの最後のシーンへのリンク、すごいですね。見なければならないものだ。

score 3 · Accepted Answer

最近、アルゴリズムの最適性の証明にバブルソートを使用しました。オブジェクトのシーケンスによって表される任意の最適解を、アルゴリズムによって検出された解に変換する必要がありました。私たちのアルゴリズムは単に「この基準でソート」であったため、最適なソリューションを悪化させることなくソートできることを証明する必要がありました。この場合、バブルソートは、隣り合って順序が間違っている2つの要素を交換するだけの優れた不変条件を備えているため、使用するのに非常に優れたアルゴリズムでした。もっと複雑なアルゴリズムを使えば、脳が溶けてしまうと思います。

ご挨拶。

score 3 · Accepted Answer

小さなデータセットに適しています。そのため、一部のqsort実装は、パーティションサイズが小さくなるとそれに切り替わります。しかし、挿入ソートはまだ高速なので、教材として以外に使用する理由はありません。

score 2 · Accepted Answer

バブルソートは実装が簡単で、データセットが小さい場合は十分に高速です。

セットがほぼソートされている場合（たとえば、1つまたは複数の要素が正しい位置にない場合）、バブルソートは十分に高速です。この場合、0インデックスからnインデックスへ、およびnインデックスから0インデックスへのトラバースをインターレースする方が適切です。。C ++を使用すると、次の方法で実装できます。

void bubbleSort(vector<int>& v) { // sort in ascending order
  bool go = true;
  while (go) {
    go = false;
    for (int i = 0; i+1 < v.size(); ++i)
      if (v[i] > v[i+1]) {
         swap(v[i], v[j]);
         go = true;
      }
    for (int i = (int)v.size()-1; i > 0; --i) 
      if (v[i-1] > v[i]) {
         swap(v[i-1], v[i]);
         go = true;
      }
  }
}

隣接する2つのアイテムの交換がチップであり、任意のアイテムの交換に費用がかかる場合に適しています。

ドナルド・クヌースは、彼の有名な「The Art of Computer Programming」で、「バブルソートは、キャッチーな名前といくつかの興味深い理論上の問題につながるという事実を除いて、それを推奨するものは何もないようです」と結論付けました。

このアルゴリズムは実装が簡単で、サポートも簡単であり、実際のアプリケーションのライフサイクルでは、サポートの労力を減らすことが重要です。

score 2 · Accepted Answer

理解と実装が非常に簡単なので、これは優れた「教育」アルゴリズムだと思います。同じ理由で小さなデータセットにも役立つ場合があります (ただし、O(n lg n) アルゴリズムの一部は実装が非常に簡単です)。

score 2 · Accepted Answer

バブルソートに関するコメントに対して、より高速な（O（nlogn）のようですが、これは実際には証明されていません）Comb Sortについて言及することを避けられません。事前計算されたテーブルを使用する場合、コムソートは少し高速であることに注意してください。コムソートはバブルソートとまったく同じですが、隣接する要素を交換することから始めない点が異なります。バブルソートと同じくらい簡単に実装/理解できます。

score 1 · Accepted Answer

私はかつて、ほとんどの場合 2 つのアイテムをソートする場合に使用しました。

次にそのコードを見たとき、誰かがそれをライブラリー・ソートに置き換えていました。彼らが最初にベンチマークしたことを願っています！

score 1 · Accepted Answer

TRS-80 モデル 1 の小さな N に対して、場合によってはそれを使用していました。for ループを使用すると、1 つのプログラム行で完全な並べ替えを実装できます。

それ以外は、教えるのに適しています。また、ほとんど並べ替えられたリストに適している場合もあります。

score 1 · Accepted Answer

そうそう、それは優れた選択メカニズムです。誰かが書いたコードにそれを見つけた場合、その人を雇うことはありません。

score 1 · Accepted Answer

コード化するのは迅速かつ簡単で、(間違いを犯すことはほぼ不可能です)。重いものを持ち上げたり、ライブラリの並べ替えをサポートしていない場合に適しています。

score 1 · Accepted Answer

これは私が実際に最も頻繁に使用する種類です。(私たちのプロジェクトでは、外部ライブラリを使用できません。)

これは、データセットが非常に小さいことが確実にわかっている場合に役立ちます。そのため、速度についてはまったく気にせず、最短で単純なコードが必要です。

バブルはあなたが行くことができる最低ではありません。最近、ちょうど 3 つの要素を並べ替える必要がある状況にありました。私はこのようなものを書きました：

// Use sort of stooge to sort the three elements by cpFirst

SwapElementsIfNeeded(&elementTop, &elementBottom);
SwapElementsIfNeeded(&elementTop, &elementMiddle);
SwapElementsIfNeeded(&elementMiddle, &elementBottom);

*pelement1 = elementTop;
*pelement2 = elementMiddle;
*pelement3 = elementBottom;

score 0 · Accepted Answer

ほとんど何もありません。代わりにQuickSortまたはSelectionSortを使用してください...！

algorithm - バブルソートは何に適していますか？

16 に答える 16

Related

Reference