バブルソートは何に役立ちますか?[閉まっている]

StackOverflow https://stackoverflow.com/questions/276113

質問

バブルソートは現実世界で何か用途がありますか?言及されているのを見るたびに、それは常に次のいずれかです。

  1. 学習できる並べ替えアルゴリズム。
  2. ソートアルゴリズムの例 ない 使用します。
役に立ちましたか？

解決

データの分散方法に依存します-何らかの仮定を立てることができるかどうか

バブルソート（または他のソート）を使用するタイミングを理解していることがわかった最高のリンクの1つは、ソートアルゴリズムのアニメーションビューです：

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

他のヒント

バブルソートは、（おそらく）非常に特定の状況下で利用可能な最速のソートです。もともとよく知られるようになったのは、厳密に分析された最初のアルゴリズム（あらゆる種類）の1つであり、限られた状況で最適であるという証拠が見つかったためです。

テープドライブに保存されているファイル、およびランダムアクセスメモリが非常に少ない（または大きなキー）ので、常に 2 レコードしかメモリにロードできないと考えてください。テープの巻き戻しは十分に遅いため、ファイル内でランダムアクセスを実行することは一般的に実用的ではありません。可能であれば、一度に2つ以下のレコードを順番に処理します。

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

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

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

最近、最適化の逸話でそれを使用することに大きな出会いがありました。プログラムには、フレームごとに深さ順に並べられたスプライトのセットが必要でした。スプライトの順序はフレーム間であまり変わらないため、最適化として、フレームごとに単一パスでバブルソートされました。これは両方向（上から下、下から上）で行われました。そのため、スプライトは常に非常に効率的なO（N）アルゴリズムでほぼソートされていました。

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

教育といえば。 並べ替えの最後のシーンへのリンクは、素晴らしいです。必見。

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

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

ごきげんよう。

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

バブルソートに関する発言への応答に抵抗することはできません（O（nlogn）と思われますが、実際には証明されていません）櫛ソート。事前に計算されたテーブルを使用する場合、Combソートは少し高速であることに注意してください。櫛の並べ替えはバブルの並べ替えとまったく同じですが、最初は隣接する要素を交換することで開始されない点が異なります。バブルソートと同じくらい簡単に実装/理解できます。

バブルソートは実装が簡単で、小さなデータセットがあれば十分に高速です。

セットがほぼソートされている場合（たとえば、1つまたは複数の要素が正しい位置にない場合）、バブルソートは十分に高速です。この場合、0インデックスからnインデックス、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つの隣接するアイテムのスワップがチップであり、任意のアイテムのスワップが高価な場合は良い場合があります。

Donald Knuthは、有名な「The Art of Computer Programming」で、「quot;バブルソートには、覚えやすい名前と、いくつかの興味深い理論上の問題につながるという事実を除いて、推奨するものは何もないようです。

このアルゴリズムは実装が容易であるため、サポートが容易であり、実際のアプリケーションライフサイクルではサポートの労力を削減することが重要です。

TRS-80モデル1の小さなNの場合に使用していました。 forループを使用すると、1つのプログラム行で完全なソートを実装できます。

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

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

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

コーディングは迅速かつ簡単であり、（間違えることはほとんど不可能です）。面倒な作業をしておらず、ライブラリの並べ替えをサポートしていない場合に適しています。

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

データセットが本当に小さいことがわかっている場合に役立ちます。そのため、速度については少し気にせず、最短で最もシンプルなコードが必要です。

バブルはあなたが行くことができる最低のものではありません。最近、正確に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;

はい、それは良い選択メカニズムです。誰かが書いたコードでそれを見つけた場合、あなたは彼を雇わない。

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

所属していません StackOverflow
scroll top