Algorytm sortowania bąbelkowego wymaga pary zagnieżdżonych pętli. Pętla zewnętrzna musi wykonać iterację raz dla każdego elementu w zestawie danych (o rozmiarze n), podczas gdy pętla wewnętrzna iteruje n razy przy pierwszym wprowadzeniu, n-1 razy po drugim i tak dalej. Rozważ cel każdej pętli. Jak wyjaśniono powyżej, sortowanie bąbelkowe jest tak skonstruowane, że przy każdym przejściu przez listę następny największy element danych jest przenoszony we właściwe miejsce. Dlatego, aby umieścić wszystkie n elementów we właściwych miejscach, zewnętrzna pętla musi zostać wykonana n razy.
Wewnętrzna pętla jest wykonywana przy każdej iteracji zewnętrznej pętli. Jego celem jest umieszczenie kolejnego największego elementu, który jest już na miejscu. Dlatego pętla wewnętrzna porównuje i zamienia sąsiednie elementy. Aby określić złożoność tej pętli, obliczamy liczbę porównań, które należy wykonać. W pierwszej iteracji zewnętrznej pętli, podczas próby umieszczenia największego elementu, musi być n – 1 porównań: pierwsze porównanie jest dokonywane między pierwszym a drugim elementem, drugie między drugim a trzecim elementem, oraz tak dalej, aż zostanie wykonane n-1 porównanie między n-1 i n-tym elementem. W drugiej iteracji zewnętrznej pętli nie ma potrzeby porównywania z ostatnim elementem listy, ponieważ został on umieszczony we właściwym miejscu w poprzednim przebiegu. Dlatego druga iteracja wymaga tylko porównań n-2. Ten wzorzec jest kontynuowany aż do przedostatniej iteracji zewnętrznej pętli, gdy tylko dwa pierwsze elementy listy są nieposortowane; oczywiście w tym przypadku konieczne jest tylko jedno porównanie. Zatem całkowita liczba porównań wynosi (n – 1) + (n – 2) … (2) + (1) = n (n – 1) / 2 lub O (n2).
Najlepszy przypadek sortowania bąbelkowego występuje, gdy lista jest już posortowana lub prawie posortowana. W przypadku, gdy lista jest już posortowana, sortowanie bąbelkowe zakończy się po pierwszej iteracji, ponieważ nie dokonano żadnej zamiany. Za każdym razem, gdy następuje przejście przez listę i nie dokonano żadnej zamiany, jest pewne, że lista jest posortowana. Sortowanie bąbelkowe jest również wydajne, gdy jeden losowy element musi zostać posortowany na posortowaną listę, pod warunkiem, że nowy element zostanie umieszczony na początku, a nie na końcu. Po umieszczeniu na początku, po prostu pojawi się we właściwym miejscu, a druga iteracja na liście wygeneruje 0 swapów, kończąc sortowanie. Przypomnij sobie, że jeśli element losowy zostanie umieszczony na końcu, sortowanie bąbelkowe traci swoją wydajność, ponieważ każdy element większy niż musi bąbelkować aż do góry.
Absolutnie najgorszym przypadkiem dla sortowania bąbelkowego jest najmniejszy element listy znajduje się na większym końcu. Ponieważ w każdej iteracji tylko największy nieposortowany element jest umieszczany we właściwej lokalizacji, gdy najmniejszy element znajduje się na końcu, będzie musiał zostać zamieniony za każdym razem na liście i nie przejdzie na początek listy, dopóki wszystkie n wystąpiły iteracje. W tym najgorszym przypadku potrzeba n iteracji n / 2 swapów, więc kolejność znowu wynosi n2.
Najlepszy przypadek: n Średni przypadek: n2 Najgorszy przypadek: n2