No of Passes in a Bubble Sort

Question

For the list of items in an array i.e. {23 , 12, 8, 15, 21}; the number of passes I could see is only 3 contrary to (n-1) passes for n elements. I also see that the (n-1) passes for n elements is also the worst case where all the elements are in descending order. So I have got 2 conclusions and I request you to let me know if my understanding is right wrt the conclusions.

Conclusion 1 (n-1) passes for n elements can occur in the following scenarios:

1. all elements in the array are in descending order which is the worst case
2. when it is not the best case(no of passes is 1 for a sorted array)

Conclusion 2 (n-1) passes for n elements is more like a theoretical concept and may not hold true in all cases as in this example {23 , 12, 8, 15, 21}. Here the number of passes are (n-2).

Answer 1

In a classic, one-directional bubble sort, no element is moved more than one position to the “left” (to a smaller index) in a pass. Therefore you must make n-1 passes when (and only when) the smallest element is in the largest position. Example:

12 15 21 23  8  // initial array
12 15 21  8 23  // after pass 1
12 15  8 21 23  // after pass 2
12  8 15 21 23  // after pass 3
 8 12 15 21 23  // after pass 4

Let's define L(i) as the number of elements to the left of element i that are larger than element i. The array is sorted when L(i) = 0 for all i. A bubble sort pass decreases every non-zero L(i) by one. Therefore the number of passes required is max(L(0), L(1), ..., L(n-1)). In your example:

23 12  8 15 21  // elements
 0  1  2  1  1  // L(i) for each element

The max L(i) is L(2): the element at index 2 is 8 and there are two elements left of 8 that are larger than 8.

The bubble sort process for your example is

23 12  8 15 21  // initial array
12  8 15 21 23  // after pass 1
 8 12 15 21 23  // after pass 2

which takes max(L(i)) = L(2) = 2 passes.

For a detailed analysis of bubble sort, see The Art of Computer Programming Volume 3: Sorting and Searching section 5.2.2. In the book, what I called the L(i) function is called the “inversion table” of the array.

Answer 2

re: Conclusion 1

all elements in the array are in descending order which is the worst case

Yep, this is when you'll have to do all (n-1) "passes".

when it is not the best case (no of passes is 1 for a sorted array)

No. When you don't have the best-case, you'll have more than 1 passes. So long as it's not fully sorted, you'll need less than (n-1) passes. So it's somewhere in between

re: Conclusion 2

There's nothing theoretical about it at all. You provide an example of a middle-ground case (not fully reversed, but not fully sorted either), and you end up needing a middle-ground number of passes through it. What's theoretical about it?