When considering comparisons for a Heap Sort, what exactly do you consider as a comparison? [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 8 years ago.

I've coded up the Heap Sort algorithm, but I'm having a hard time deciding what should be considered a comparison. I assumed the following would contribute towards the comparisons but the results I obtain seem off to me (by a lot maybe?) here's the code

       public class heapsort{
      static int counter = 0;

      public static void main(String[] args) { 
         //int[] a1={1, 16, 2, 3, 14, 4, 5, 12, 7, 10, 8, 9, 17, 19, 21, 23, 26, 27}; 

            int[] a1 = {1, 2};
            System.out.println(sort(a1)); 
         for(int i=0;i<a1.length;i++){ 
            System.out.print(a1[i] + " "); 
         } 
      } 

      private static int[] a; 
      private static int n; 
      private static int left; 
      private static int right; 
      private static int largest;

      public static void buildheap(int[] a){ 
         n= a.length-1; 
         for(int i= n/2; i >= 0; --i){ 
            maxheap(a,i); 
         } 
      } 

      public static void maxheap(int[] a, int i){ 
         left=2*i; 
         right=2*i+1; 
         if(left <= n && a[left] > a[i]){ 
            counter++;
            largest=left; 
         } 
         else{ 
            counter++;
            largest=i; 
         } 

         if(right <= n && a[right] > a[largest]){ 
            counter++;

            largest=right; 
         } 
         if(largest!=i){ 
            counter++;     
            exchange(i,largest); 
            maxheap(a, largest); 
         } 
      } 

      public static void exchange(int i, int j){ 
         int t=a[i]; 
         a[i]=a[j]; 
         a[j]=t; 
      } 

      public static int sort(int []a0){ 
         a=a0; 
         buildheap(a); 

         for(int i=n;i>0; --i){ 
            exchange(0, i); 
            n=n-1; 
            maxheap(a, 0); 
         } 
         return counter;
      }       
   }

I know some of the counters might be wrong, suggestions?

Answer 1

Count comparisons of your array, sometimes/always "a". EG: "a[left] > a[i]". You could add a counter for the comparisons as a global, and ++ it each time you do a comparison to get a comparison count.

BTW, heap sort is interesting theoretically, but it's not stable, and isn't generally as fast as timsort, nor does it take advantage of partially sorted data as well.

Answer 2

You generally only count element comparisons, not integer comparisons, even though the elements in your array are integers.

To make this make a bit more sense - if you were to change the array to an array of strings (for example), only count the number of string comparisons. String comparisons are generally way more expensive than integer comparisons (and it would be even more so if you have a large object with many fields), so only counting these makes sense.

So these compare elements:

a[left] > a[i]
a[right] > a[largest]

These just compare integers:

i >= 0
left <= n
right <= n
largest != i
i > 0

I'd suggest writing a compare function that also increases your count (and just replacing the above 2 element comparisons with it and removing other places where you increase the count). I also suggest sticking to convention in what the function returns.

Your function can just look like this: (pre-Java 7 you'll have to use Integer.valueOf(a).compareTo(b) instead)

int compare(int a, int b)
{
  counter++;
  return Integer.compare(a, b);
}

So a[left] > a[i] would become compare(a[left], a[i]) > 0, and similarly for the other one.

A Comparator would make for a more generic solution, but it is probably a bit overkill in this case.