1

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?

3

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.