3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The 'for' loop always performs $n$ comparisons (regardless of swaps). So as long as the 'while' loop runs $O(n)$ times, the runtime will be $O(n^2)$. An easy example showing this is just placing the minimum element in the end of the list $\endgroup$ – lox May 18 at 22:56
  • $\begingroup$ @lox thanks for the reply! hmm I think I may be taking the $n$ in $O(n)$ too literally.. because when I think of $n$, I think of the length of the list... and the 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 of while loop runs increases in a linear pattern as the size of $n$ increases? but how does that equate to $n^2$ comparisons? $\endgroup$ – clark May 18 at 23:02
  • $\begingroup$ Suppose you implement the psuedocode described in your question. Elements of list that "win" comparisons get bubbled up, and continue being compared to their adjacent. But elements that "lose" (are smaller) get shifted one index backwards, and are not touched until the next 'while' iteration. $\endgroup$ – lox May 18 at 23:06
  • $\begingroup$ So if an element belongs to the beginning of the sorted list (or is lesser than $\Omega (n)$ elements) happens to occur after $\Omega (n)$ greater elements, you will need $\Omega (n)$ 'while' iterations to shift him back $\endgroup$ – lox May 18 at 23:09
  • $\begingroup$ @lox so the number of 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$ – clark May 18 at 23:50
3
$\begingroup$

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}. $$

$\endgroup$
2
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.