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?

Improve this question
2
  • 1
    Possible duplicate of programmers.stackexchange.com/questions/117304/… Commented Apr 24, 2015 at 0:37
  • @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. Commented Apr 24, 2015 at 4:01

1 Answer 1

Reset to default
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.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.