Algoritmen för bubblasortering kräver ett par kapslade slingor. Den yttre slingan måste itera en gång för varje element i datamängden (av storlek n) medan den inre slingan itererar n gånger första gången den matas in, n-1 gånger den andra, och så vidare. Tänk på syftet med varje slinga. Som förklarats ovan är bubblasortering strukturerad så att vid varje passering genom listan flyttas det näst största elementet i datan till rätt plats. Därför måste den yttre slingan utföras n gånger för att få alla n-element på sina rätta platser.
Den inre slingan körs på varje iteration av den yttre slingan. Syftet är att sätta det näst största elementet på plats. Den inre slingan gör därför jämförelse och byte av intilliggande element. För att bestämma komplexiteten hos denna slinga beräknar vi antalet jämförelser som måste göras. Vid den första iteration av den yttre slingan, medan man försöker placera det största elementet, måste det finnas n – 1 jämförelser: den första jämförelsen görs mellan det första och det andra elementet, det andra görs mellan det andra och tredje elementet, och så vidare tills n-1: e jämförelsen görs mellan n-1 och n-elementet. Vid den andra iterationen av den yttre slingan finns det inget behov av att jämföra mot det sista elementet i listan, eftersom det placerades på rätt plats vid föregående pass. Därför kräver den andra iterationen endast n-2-jämförelser. Detta mönster fortsätter tills den näst sista iterationen av den yttre slingan när endast de första två elementen i listan är osorterade; i detta fall är det klart att endast en jämförelse är nödvändig. Det totala antalet jämförelser är därför (n – 1) + (n – 2) … (2) + (1) = n (n – 1) / 2 eller O (n2).
Det bästa fallet för bubblasortering uppstår när listan redan är sorterad eller nästan sorterad. Om listan redan är sorterad kommer bubblasorteringen att avslutas efter den första iterationen, eftersom inga byten gjordes. Varje gång som ett pass görs genom listan och inga byten gjordes är det säkert att listan är sorterad. Bubblesortering är också effektiv när ett slumpmässigt element måste sorteras i en sorterad lista, förutsatt att nytt element placeras i början och inte i slutet. När den placeras i början bubblar den helt enkelt upp till rätt plats, och den andra iterationen genom listan genererar 0 byten och slutar sorteringen. Kom ihåg att om det slumpmässiga elementet placeras i slutet förlorar bubblasorteringen sin effektivitet eftersom varje element som är större än det måste bubbla hela vägen upp till toppen.
Det absolut värsta fallet för bubblasortering är när den minsta delen av listan är i den stora änden. Eftersom bara det största osorterade elementet placeras på rätt plats i varje iteration, när det minsta elementet är i slutet, måste det bytas varje gång genom listan och det kommer inte att komma fram till listan tills alla n iterationer har inträffat. I värsta fall tar det n upprepningar av n / 2-byten så att ordern återigen är n2.
Bästa fall: nGenomsnittligt fall: n2 Värsta fall: n2