How to count sort comparison

Question

When it is said that this sort has M number of comparisons what does it mean?

As an example:

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

Has

for i = 1 to n-1

or

for(int i = 0 ; i < n-1; i++)

is this comparison (i < n-1) taken into account?

Or in merge sort, beside the main comparison:

 if (v[first1]<v[first2])

at the end of a used function it is written:

 while (first1 <= last1)
 temp[index++] = v[first1++];
 while (first2 <= last2)
 temp[index++] = v[first2++];
 for (index = first; index <= last; index++)
 v[index] = temp[index];

Are these comparisons are taken into account?

• Jay Elston: Possible duplicate of programmers.stackexchange.com/questions/117304/…
• zahmati: @JayElston, Could you explain how that question answers about what commands to be taken into account? btw, I do not care about big o. I need exact number of comparison.

Answer 1

When you find a statement like "M number of comparisons" about sorting algorithms in literature, the author typically means the number of comparisons between the sorted elements, not the comparisons of something like loop indexes. So if you are asked this in a university assignment, I would guess that this is the number which is meant (but to make that clear, if you give an answer, why not add a note describing exactly what you counted).

In fact, this assumes that the predominant operations in a sorting algorithm are comparisons and "swaps", and that there are not more loop iterations than comparisons between the sorted elements. When you assume the latter, for calculating Big-O it is irrelevant if you count the "loop index comparisons" or not.

Furthermore, note that a term like "exact number of comparisons" instead of "O(number of comparisons)" makes only sense for a specific implementation of an algorithm, not "for an algorithm" in general. So when you try to compare the number of comparisons of your implementation of bubble sort to a different implementation from a different author, you have to make sure you do not compare apples and oranges. That is why comparisons in terms of "Big-O" makes more sense when comparing algorithms on a theoretical level.

However, from a more practical point of view, counting the exact "number of comparisons" (or swaps) will indeed make sense when it comes to speed comparisons of specific sorting implementations on real-world data.