CODEWITHSUNDEEP
javainsertion-sortselection-sort
rubikscube09
rubikscube09

Reputation: 159

How to count comparisons in selection and insertion sorts?

I am writing 2 different sorts, one being selection the other being insertion. The following is my insertion sort method

public static void  iSort(String[] array)
{
  int i, j, k;
  String temp; 
  for(i = 1; i<array.length; i++)
  {
   k=i;
   for(j = k-1; j>=0 && array[j].compareTo(array[k])>0; j--)
   {
    ccounter++;
     temp = array[j];
     array[j] = array[k];
     array[k] = temp;
     k--;
   }
   }
 }

where ccounter is a static class variable. When I test this using a 1000 element array of strings, i get a value of 239507. However, when I test with a correctly ordered array of strings, I get a value of zero, which I know is incorrect as the best case performance is n comparisons for n terms. I wonder if my method is written incorrectly, or if the counter is placed incorrectly

Upvotes: 1

Views: 1627

Answers (2)

arunmoezhi
arunmoezhi

Reputation: 3200

increment counter for every execution of inner loop and do the comparison after incrementing the counter

public static void  iSort(String[] array)
{
  int i, j, k,ccounter=0;
  String temp; 
  for(i = 1; i<array.length; i++)
  {
        k=i;
        for(j = k-1; j>=0; j--)
        {
                 ccounter++; //increment counter for every execution of inner loop
                 //better to do integer comparison than string comparison
                 if(Integer.parseInt(array[j]) <= Integer.parseInt(array[k]))
                 {
                     break;
                 }
                 temp = array[j];
                 array[j] = array[k];
                 array[k] = temp;
                 k--;
        }
   }
}

Upvotes: 0

NPE
NPE

Reputation: 500843

The issue is that, if you exit the loop because compareTo() has returned false, you are not counting that final comparison.

If I were writing this, I'd wrap the comparison code in a function that would call compareTo() and increment the counter. I would then use this wrapper function exclusively, to do all the comparisons. This way there's no chance of miscounting.

Upvotes: 1

Related Questions