do you include the step before a comparison is made in the number of iterations a sorting algorithm takes?

Question

Im having a bit of a mind blank, as the question states; when you are counting the number of steps an algorithm takes to complete do you have to include a step where no comparisons have been made yet?

for example:

if you have a list: 5,3,7

and you perform a bubble sort on it. It would;

1) compare 5 and 3 and swap them as 5>3. The list is now 3,5,7

2) compare 5 and 7 with no change as 5<7. The list is now 3,5,7

3) compare 3 and 5 with no change as expected. The list is still 3,5,7

4) compare 5 and 7 with no change as expected. The list is still 3,5,7

now would the number of iterations taken be 4 or 5? ... or have i got that completely wrong?

Thanks

Answer 1

It sometimes helps to look at / think about the code: (taken from Wikipedia)

procedure bubbleSort( A : list of sortable items )
   repeat     
     swapped = false
     for i = 1 to length(A) - 1 inclusive do:
       // this is the start of an iteration
       if A[i-1] > A[i] then
         swap( A[i-1], A[i] )
         swapped = true
       end if
       // this is the end of an iteration
     end for
   until not swapped
end procedure

Based on the above, it should be easy to see that we only count an iteration when we're actually doing a comparison.

So it would be 4 iterations.

---

As a technicality, you could also talk about iterations in terms of the repeat ... until loop, which would give you quite different results.

And the 'steps' can certainly be split up into a lot smaller parts.

For ambiguities similar to the above, we tend to stick to big-O notation, which really just gives us a rate of growth of an algorithm's running time.

Answer 2

IMHO, at the point of time when no steps were performed yet, the step count = 0. After performing one step, the step count = 1. I truly can't fanthom how you got to a point that performing 4 steps is to be considered five..

Anyways, remember that it's usually analyzed as O(f(n)) where term not-related-to-N like +-constant i.e. +-1 or +-100 are simply dropped off.

Answer 3

You have performed 4 iterations. This is why number of iterations is 4.

Algorithm

//... some precondition steps

iteration( for... )  {       <
  //...                      < iteration steps
}                            <