8.4.2. Bubble Sort Analysis¶

The following visualization illustrates the running time analysis of Bubble Sort.

1 / 24 Settings

<<<>>>

What is the cost of Bubblesort?

1. 180
2. 71
3. 32
4. 33
5. 94
6. 125

$i = 0$

$i = 1$

$i = 2$

$i = 3$

$i = 4$

$n - 1$

$n - 1$

Saving...
Server Error
Resubmit

Thus, Bubble Sort's running time is roughly the same in the best, average, and worst cases.

The number of swaps required depends on how often a record's value is less than that of the record immediately preceding it in the array. We can expect this to occur for about half the comparisons in the average case, leading to $\Theta(n^2)$ for the expected number of swaps. The actual number of swaps performed by Bubble Sort will be identical to that performed by Insertion Sort.

Here are some review questions to check your understanding of Bubble Sort.