バブルソート

バブルソートの最悪ケースと平均の複雑さは${\displaystyle O(n^{2})}$、 どこ${\displaystyle n}$は、ソート対象のアイテム数です。ほとんどの実用的なソートアルゴリズムは、最悪の場合または平均的な複雑さが大幅に改善されており、多くの場合、${\displaystyle O(n\log n)}$他にも${\displaystyle O(n^{2})}$挿入ソートなどのソートアルゴリズムは、一般的にバブルソートよりも高速で、複雑さも変わりません。そのため、バブルソートは実際にはほとんど使用されていません。

挿入ソートと同様に、バブルソートは適応型であり、クイックソートのようなアルゴリズムよりも優位に立つことができます。つまり、平均時間計算量は劣るものの、リストが既にほとんどソートされている（反転が少ない）場合には、これらのアルゴリズムよりも優れたパフォーマンスを発揮する可能性があります。たとえば、バブルソートは${\displaystyle O(n)}$既にソートされているリストに対してはクイックソートは依然としてその全機能を実行します。${\displaystyle O(n\log n)}$選別プロセス。

どのようなソートアルゴリズムでも作成できますが${\displaystyle O(n)}$事前にソートされたリストでは、アルゴリズムを実行する前にリストをチェックするだけでパフォーマンスを向上させることができますが、ほぼソートされたリストでは、その効果を再現するのはより困難です。

バブルソートのパフォーマンスは、要素がソート中に移動しなければならない距離と方向によって決まります。要素は異なる方向に異なる速度で移動するためです。リストの末尾に向かって移動しなければならない要素は、連続したスワップに参加できるため、速く移動できます。たとえば、リストの中で最大の要素はすべてのスワップに勝つため、リストの先頭付近から始まっても最初のパスでソートされた位置に移動します。一方、リストの先頭に向かって移動しなければならない要素は、1回のパスで1ステップより速く移動できないため、先頭に向かって非常にゆっくりと移動します。最小の要素がリストの末尾にある場合、${\displaystyle n-1}$先頭に移動するためのパス。このため、これらのタイプの要素は、イソップ寓話「ウサギとカメ」の登場人物にちなんで、それぞれウサギとカメと名付けられました。

バブルソートの速度を向上させるために、タートルを排除するためのさまざまな試みが行われてきました。カクテルソートは、開始から終了まで進み、その後逆方向に進み、終了から開始まで進む双方向バブルソートです。タートルをかなりうまく移動できますが、${\displaystyle O(n^{2})}$最悪の場合の複雑さ。コームソートは大きな間隔で区切られた要素を比較し、リストを滑らかにするために間隔をどんどん小さくしていく前に、タートルを非常に速く移動させることができます。その平均速度は、クイックソートのようなより高速なアルゴリズムに匹敵します。

数値の配列「5 1 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回全体を走査する必要があります。

3回目のパス

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

擬似コードでは、このアルゴリズムは（0から始まる配列で）次のように表現できます。

procedure bubbleSort ( A :ソート可能なアイテムのリスト) n := length ( A ) repeat swapped := false for i := 1 to n - 1 inclusive do { このペアが順不同の場合 } if A [ i - 1 ] > A [ i ] then { それらを交換して、何かが変更されたことを記憶する } swap ( A [ i - 1 ] , A [ i ]) swapped := true end if end for until not swapped end procedure

バブルソートアルゴリズムは、n回目のパスでn番目に大きい要素を見つけて最終位置に配置するという点に着目することで最適化できます。そのため、内側のループでは、 n回目の実行時に最後のn -1個の項目を参照する必要がなくなります。

procedure bubbleSort ( A :ソート可能なアイテムのリスト) n := length ( A ) repeat swapped := false for i := 1 to n - 1 inclusive do if A [ i - 1 ] > A [ i ] then swap ( A [ i - 1 ] , A [ i ]) swapped := true end if end for n := n - 1 until not swapped end procedure

より一般的には、1回のパスで複数の要素が最終位置に配置される場合があります。特に、各パスの後、最後のスワップ以降のすべての要素はソートされ、再度チェックする必要はありません。これにより、多くの要素をスキップできるため、最悪の場合の比較回数が約50%改善されます（ただし、スワップ回数は改善されません）。また、新しいコードが変数を包含するため、複雑さはほとんど増えませんswapped。

これを擬似コードで表現すると、次のようになります。

procedure bubbleSort ( A :ソート可能なアイテムのリスト) n := length ( A ) repeat newn := 0 for i := 1 to n - 1 inclusive do if A [ i - 1 ] > A [ i ] then swap ( A [ i - 1 ] , A [ i ]) newn := i end if end for n := newn until n ≤ 1 end procedure

カクテルシェーカーソートなどの代替的な改良版は、隣接するアイテムを繰り返し比較して交換するという同じ考え方を維持しながら、バブルソートのパフォーマンスを向上させようとするものです。