There is an ambiguity in the specification of the bubble sort algorithm given in the start of the post. In fact, there are multiple versions of the bubble sort algorithm.
Variations of bubble sort.
One simple version is presented in exercise 2.2. of CLRS, version 2 which does $n-1$ iterations, where each iteration performs one less comparison than the iteration before.
Another simple version is presented in this Wikipedia article, which stops once no swap is performed in an iteration.
There are two improved versions. The first one combines the advantage of the two simple versions. The other one goes further to identify more elements that have been settled down in each iteration.
It goes without saying that it is important to specify which version of the bubble sort we are talking about. It becomes critical when we want to analyse the time-complexity.
While specifying which version of the bubble sort should be critical, all complexity-analysis in this answer does not depend on any particular version, thanks to the usage of inversion number.
Number of swaps
Regardless of which version of bubble sort is used for a given list, the number of swaps is the same.
Lemma. The number of swaps performed by a bubble sort on a given list is the inversion number of the given list.
Proof: Each swap of two adjacent elements decreases the inversion number by 1. The inversion number of a sorted list is 0.
What is the bound for the number of swaps performed by a bubble sort, assuming all elements in the input list are distinct?
- In the best case when the input list is sorted, no swap is used.
- In the worst case when the input list is sorted reversely, $n(n-1)/2$ swaps are used.
- Suppose each permutation of all elements is equally likely to be given as the input list. For each pair $p$ of indices, if it is an inversion for a permutation $\sigma$, then it is not an inversion for the corresponding permutation that is $\sigma$ with the elements at $p$ switched. So $p$ is an inversion for half of all permutations. That means $p$ is an inversion with a probability of $\frac12$. Since there are $n(n-1)/2$ pairs of indices, there are $\frac12n(n-1)/2$ inversions in an list on average. That is, $n(n-1)/4$ swaps are performed by bubble sort on average.
Number of comparisons.
Since a swap can only happens only when there is a comparison (that finds an inversion), the number of comparisons must be no less than the number of swaps. The number of swaps given above provides a lower bound for the number of comparisons. The number of comparisons is at most $(n-1)^2$. These holds regardless of which version of bubble sort is used.
- In the best case when the input list is sorted, all versions except the one in CLRS use $n-1$ comparisons.
- In the worst case when the input list is sorted reversely, $\Theta(n^2)$ comparison are used.
- Suppose each permutation of all elements is equally likely. $\Theta(n^2)$ comparison are used on average.
while
loop only runs $n$ times in the worst case. but... I'm guessing, what you mean by $O(n)$ times, is that the number ofwhile
loop runs increases in a linear pattern as the size of $n$ increases? but how does that equate to $n^2$comparisons
? $\endgroup$while
loops is determined by the greatest distance between the correct position and the current position of an element that is further down the list than it should be $+ 1$? i.e. if the list is[3,2,1,0,4]
, $0$ is the furthest from it's correct position, it will shift $3$ times, taking $3$while
loops. $+ 1$while
loop where no swaps are made and it terminates. this list does $16$comparisons
, $6$swaps
and $4$while
loops. $\endgroup$