バブルソート

PerformanceEdit

バブルソートの複雑さは、最悪の場合と平均でО（n2）です。ここで、nはソートされるアイテムの数です。ほとんどの実用的なソートアルゴリズムは、最悪の場合または平均的な複雑さが大幅に向上し、多くの場合O（n log n）です。挿入ソートなどの他のО（n2）ソートアルゴリズムでさえ、一般にバブルソートよりも高速に実行され、それほど複雑ではありません。したがって、バブルソートは実用的なソートアルゴリズムではありません。

バブルソートが他のほとんどのアルゴリズムよりも優れている唯一の重要な利点は、挿入ソートではなくクイックソートでさえ、リストがソートされていることを検出できることです。効率的にアルゴリズムに組み込まれています。リストがすでにソートされている場合（最良の場合）、バブルソートの複雑さはO（n）のみです。対照的に、他のほとんどのアルゴリズムは、平均的なケースの複雑さが優れている場合でも、セットに対してソートプロセス全体を実行するため、より複雑になります。ただし、挿入ソートはこの利点を共有するだけでなく、実質的にソートされた（反転の数が少ない）リストでのパフォーマンスも向上します。さらに、この動作が必要な場合は、アルゴリズムを実行する前にリストを確認することで、他のアルゴリズムに簡単に追加できます。

大規模なコレクションの場合は、バブルソートを回避する必要があります。逆順のコレクションの場合は効率的ではありません。

Rabbits and TurtlesEdit

並べ替え中に要素が移動する必要のある距離と方向によって、バブルソートのパフォーマンスが決まります。要素はさまざまな方向にさまざまな速度で移動します。リストの最後に向かって移動する必要がある要素は、連続するスワップに参加できるため、すばやく移動できます。たとえば、リスト内の最大の要素がすべてのスワップに勝つため、次の場所に移動します。最初のパスでソートされた位置は、最初のパスから始まったとしてもです。一方、リストの最初に移動する必要がある要素は、パスごとに1ステップより速く移動できないため、要素は最初のパスに非常にゆっくりと移動します。最小の要素はリストの最後にあり、最初に移動するにはn-1パスかかります。これにより、これらのタイプの要素は、Aesopの寓話の文字にちなんで、それぞれウサギとカメと呼ばれるようになりました。亀とうさぎ。

さまざまなバブルソートの速度を改善するために、カメを排除するための努力がなされてきました。カクテルソートは、最初から最後まで行き、次にそれ自体を逆にして、最後から最初まで行く双方向のバブルソートです。カメをかなりうまく動かすことができますが、O（n2）の最悪の場合の複雑さを保持します。コムソートは、大きなギャップで区切られた要素を比較し、リストを滑らかにするためにますます小さなギャップに進む前に、カメを非常にすばやく移動させることができます。その平均速度は、クイックソートなどのより高速なアルゴリズムに匹敵します。

ステップバイステップの例編集

数値の配列「51 4 2 8」を取得し、配列を低いものから並べ替えます。バブルソートを使用した最大数への数。各ステップで、太字で書かれた要素が比較されています。 3つのパスが必要になります。

最初のパス（5 1 4 2 8）→（1 5 4 2 8）、ここでは、アルゴリズムが最初の2つの要素を比較し、5 > 1.（1 5 4 2 8）→（1 4 5 2 8）、5からスワップ> 4（1 4 5 2 8）→（1 4 2 5 8）、5 > 2（1 4 2 5 8）→（1 4 2 5 8）からスワップします。これらの要素はすでに順序付けられているため（8 > 5）、アルゴリズムはそれらを交換しません。 2番目のパス（1 4 2 5 8）→（1 4 2 5 8）（1 4 2 5 8）→（1 2 4 5 8）、4 > 2（ 1 2 4 5 8）→（1 2 4 5 8）（1 2 4 5 8）→（1 2 4 5 8）

これで、配列はすでにソートされていますが、アルゴリズムはそれが完了したかどうかを認識していません。アルゴリズムは、ソートされていることを知るために、スワップなしで1つのパス全体を必要とします。