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?
2
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.