Bubble Sort with "while" loop - why is average case n^2?

Question

If Bubble Sort is written as:

    while True:
        False
        for i in (0 to n - 2):
            if list[i] > list[i + 1]:
                swap.(list[i], list[i + 1])
                True
    return list

(where n is len(list))

Seems to me that in the worst case (a list in descending order):

• the while loop runs $n$ times
• the for loop runs $n - 1$ times per while loop $∴$ there will be $n^2 - n$ comparisons
• the list is in decreasing order so there will ultimately be $(n^2 - n)/2$ swaps
• $∴$ worst case is $O(n^2)$

In the best case (a list already sorted):

• the while loop runs $1$ time
• there will be $n - 1$ comparisons
• the list is already sorted so there will ultimately be $0$ swaps
• $∴$ best case is $\Omega(n)$

So for the average case...

• the while loop will run more than $1$ time but less than $n$ times
• there will be more than $n - 1$ but less than $n^2 - n$ comparisons

• there will be more than $0$ but less than $(n^2 - n)/2$ swaps, depending on the state of the list

• $∴$ how can we show that the average case is also $n^2$ and $\Theta(n^2)$?

I don't understand where $n^2$ can be observed?

Is it because the number of swaps will always be equal to $(n^2 - n)/x$, where $x$ is determined by the state of the list?

And, as stated here (and in other places), on average, with uniform distribution, the number of swaps would be $(n^2 - n)/4$, which is half the worst case?

I'm confused :( Any help would be appreciated! Thank you.

Answer 1

Let's prove a more general result:

Any sorting algorithm which only swaps adjacent elements makes $\Omega(n^2)$ swaps on average.

Let us assume that the elements being sorted are $1,\ldots,n$, and their positions are $i_1,\ldots,i_n$. We need to move element $j$ from position $i_j$ to position $j$. Each swap changes the position of two elements by 1. It follows that the number of swaps is at least $$ \frac{1}{2} \sum_{j=1}^n |i_j - j|. $$ The marginal distribution of each $i_j$ is uniform over $\{1,\ldots,n\}$, hence the expected number of swaps is at least $$ \frac{1}{2n} \sum_{i=1}^n \sum_{j=1}^n |i-j| = \frac{n^2-1}{6}. $$

Answer 2

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.