What is the best-case number of array item comparisons in this algorithm, in terms of n?

Question

The Smart Bubble Sort.

Preconditions: x1, x2, ... , xn is in U, a set that is totally ordered by <, and n ≥ 2.

Postconditions: x1 ≤ x2 ⋯ ≤ xn.

  s ← false    // s = "array is sorted"

  i ← 1
  while ¬s do

---  j ← 1
     s ← true    // array is sorted UNLESS ...
     while j ≤ n − i do
      --  if xj > xj + 1 then
        -  swap xj and xj + 1
        -  s ← false    // ... a swap is made

      -- j ← j + 1

--- i ← i + 1

This algorithm takes advantage of the observation that if no swaps are made, then the array must be in order.

My Question is what are the best and worse case number of array item comparisons in this algorithm, in terms of n? I have determined that the best case data sets occur in order and the worse case data sets occur in reverse order, I have came to the conclusion of (n-1) and 0(n) but this is not correct. What are the comparisons in terms of n?

Answer 1

You're right about what input orderings produce the best and worst case results. To get a better idea of the number of comparisons, you could start by running the algorithm by hand (using pencil and paper) for n=3, n=4, n=5 and try to understand the pattern.