What counts as a comparison in algorithm analysis?

Question

MAIN QUESTION: When keeping track of comparisons, what actually counts as a comparison? Should I only count comparisons between array items since that's what the algorithm is meant for or is it more widely accepted to count every single comparison?

Currently, I am trying to wrap my head around the fact that I'm told that the theoretical number of comparisons for the worst case bubble sort algorithm is as follows:

Amount of comparisons:

(N-1) + (N-2) + (N-3) + ... + 2 + 1 = (N*(N-1))/2 = (N^2-N)/2 < N^2

So according to the formula (N^2-N)/2, with an input size (N) of 10, I would get a total of 45 comparisons. However, it is mentioned that this calculation only applies to the comparison operation in the inner loop of this pseudo code:

for i:=1 to N-1 do 
{
    for j:=0 to N-i do
    {
        if A[j] > A[j+1] // This is the comparison that's counted.
        {
            temp := A[j]
            A[j] := A[j+1]
            A[j+1] := temp
        }
    }
}

Now in Java, my code looks like this:

public int[] bubble(int[] array) 
    {
        int comparisons = 0;
        int exchanges = 0;
        int temp;
        int numberOfItems = array.length;
        boolean cont = true;  
        
        comparisons++; // When pass == numberOfItems, a comparison will be made by the for loop that wouldn't otherwise be counted.
        for (int pass=1; pass != numberOfItems; pass++) 
        { 
            comparisons = comparisons + 2; // Counts both the outer for loop comparison and the if statement comparison.

            if (cont) // If any exchanges have taken place, cont will be true.
            {    
                cont = false;  
                comparisons++; // Counts the inner for loop comparison

                for (int index = 0; index != (numberOfItems - pass); index++) 
                {
                    comparisons++; // Counts the if statement comparison.

                    if (array[index] > array[index+1]) 
                    {
                        temp = array[index];
                        array[index] = array[index+1];
                        array[index+1] = temp;
                        cont = true;
                        exchanges++;
                    }  // end inner if              
                }  // end inner for            
            }
            else
            {
                break;  // end outer if
            }
        }      
        
        System.out.println("Comparisons = " + comparisons + "\tExchanges = " + exchanges);
        return array;
    }

After performing the worst case scenario on my code (using an array with 10 elements that are in the reverse order), I have gotten a total of 73 comparisons. This seems like a crazy high overshoot of the theoretical result which was 45 comparisons. This feels right to me though since I've accounted for all for loops and if statements.

Any help is greatly appreciated!

EDIT: I have noticed an error in my total comparison count for my inner loop. I wound up counting the inner loop twice before, but now it is fixed. Instead of getting 118 comparisons, I now get 73. However, the question still stands.

Answer 1

When measuring the number of comparisons in a sort, you only count comparisons between the array items. You count them whether or not they're actually in the array when you compare them.

The idea is that, instead of simple integers, the array might contain things that take a long time to compare. An array of of strings, for example, can be bubble-sorted using N(N-1)/2 string comparions, even though a single string comparison might require many other operations, including many comparisons of individual characters.

Measuring the performance of a sorting algorithm in terms of the number of comparisons makes the measurement independent of the type of things being sorted.

Answer 2

the comparison variable should only be incremented after the if statement has been reached in the execution of the code. The if statement is only reached if the condition stated in the outer and inner for loop have been met therefore the code should be like this. Also dont forget to change the condition in the for loops from using != to <= The new java code:

public int[] bubble(int[] array) 
   {
        int comparisons = 0;
        int exchanges = 0;
        int temp;
        int numberOfItems = array.length;
        boolean cont = true;  


        for (int pass=1; pass <= numberOfItems; pass++) 
        { 


            if (cont) // If any exchanges have taken place, cont will be true.
            {    
                cont = false;  

                for (int index = 0; index <= (numberOfItems - pass); index++) 
                {

                    if (array[index] > array[index+1]) 
                    { comparison++;
                        temp = array[index];
                        array[index] = array[index+1];
                        array[index+1] = temp;
                        cont = true;
                        exchanges++;
                    }  // end inner if              
                }  // end inner for            
           }

        }     
         comparison++; // here you increment by one because you must also count the comparison that failed

        System.out.println("Comparisons = " + comparisons + "\tExchanges = " + exchanges);
        return array;
    } 

Answer 3

In evaluating sorting algorithms, it is common to count all comparisons between array elements as having equivalent cost, while ignoring comparisons between things like array indices. The basic concept is that in order for sorting operations to remain distinctly different from radix partitioning, the size of the items being sorted would need to increase as the number of them increased. Suppose, for example, one had an array of 1,000,000,000 char values and wanted to sort them. While one could use Quicksort, bubble sort, or something else, a faster approach would simply be to use an int[65536] and count how many of each value there are. Even if one needed to sort items which had char keys, the best way to do that would be to determine where to place the last item with a key of 0 (the number of items with a key of zero, minus one), where to place the last item with a key of 1 (number of items with keys of 0 or 1, minus one), etc. All such operations would take time proportional to the number of items plus the number of possible key values, without any lg(N) factor.

Note that if one ignores "bookkeeping" costs, algorithms like Quicksort aren't quite optimal. A sorting algorithm which is designed to maximize the amount of information gained from each comparison may do slightly fewer comparisons. Unless comparisons are very expensive, however, such a sorting algorithm would likely waste more time being "smart" than it would have spent being "stupid".

One issue I haven't seen discussed much, though I would think it could offer significant benefit in many real-world cases, would be optimizing sequences of comparisons between items that are known to be in a narrow range. If while performing a Quicksort on a series of thousand-character path names, one is processing a partition whose entries are all known to between two names that share the first 950 characters, there would be no need to examine the first 950 characters of any names in that partition. Such optimizations would not likely be meaningful in big-O terms unless key length was a parameter, but in the real world I would expect it could sometimes have an order-of-magnitude impact.