バブルソートのアルゴリズムには、ネストされたループのペアが必要です。外側のループは（サイズnの）データセット内の要素ごとに1回繰り返す必要がありますが、内側のループは最初に入力されたときにn回、2番目にn-1回繰り返されます。各ループの目的を検討してください。上で説明したように、バブルソートは、リストを通過するたびに、データの次に大きい要素が適切な場所に移動するように構成されています。したがって、n個の要素すべてを正しい場所に配置するには、外側のループをn回実行する必要があります。
内側のループは、外側のループの各反復で実行されます。その目的は、次に大きな要素を配置することです。したがって、内部ループは隣接する要素の比較と交換を行います。このループの複雑さを判断するために、実行する必要のある比較の数を計算します。外側のループの最初の反復では、最大の要素を配置しようとしているときに、n -1回の比較が必要です。最初の比較は最初の要素と2番目の要素の間で行われ、2番目の比較は2番目と3番目の要素の間で行われます。 n-1番目とn番目の要素の間でn-1番目の比較が行われるまで、以下同様です。外側のループの2回目の反復では、リストの最後の要素と比較する必要はありません。これは、前のパスの正しい場所に配置されているためです。したがって、2回目の反復ではn-2回の比較のみが必要です。このパターンは、リストの最初の2つの要素のみがソートされていないときに、外側のループの最後から2番目の反復まで続きます。この場合、明らかに1つの比較のみが必要です。したがって、比較の総数は（n-1）+（n-2）…（2）+（1）= n（n-1）/ 2またはO（n2）です。
バブルソートの最良のケースは、リストがすでにソートされているか、ほぼソートされている場合に発生します。リストがすでにソートされている場合、スワップが行われなかったため、バブルソートは最初の反復後に終了します。リストを通過し、スワップが行われなかった場合は常に、リストがソートされていることは確実です。バブルソートは、新しい要素が最後ではなく最初に配置されている場合、1つのランダムな要素をソート済みリストにソートする必要がある場合にも効率的です。最初に配置すると、正しい場所にバブルアップするだけで、リストの2回目の反復で0のスワップが生成され、並べ替えが終了します。ランダム要素を最後に配置すると、バブルソートの効率が低下することを思い出してください。これは、それより大きい各要素が一番上までバブルする必要があるためです。
バブルソートの絶対的な最悪のケースは、リストの最小要素は大きい方の端にあります。各反復では、ソートされていない最大の要素のみが適切な場所に配置されるため、最小の要素が最後にある場合、リストを介して毎回スワップする必要があり、すべてのnまでリストの先頭に移動しません。反復が発生しました。この最悪の場合、n / 2スワップのn回の反復が必要になるため、順序もn2になります。
最良の場合：n平均の場合：n2最悪の場合：n2