title: What's the exact number of compares that it takes insertion sort to compare numbers in this array?
body: <p>If I have an array A = &lt;0, 15, 5, 1, 0, 20, 25, 30, 35, 40>. When i write the code to count the comparisons, I am confused on where to add a counter, because I'm afraid there might be repeated counts.</p>
  
  <p>Nevertheless, it says there are 15 comparisons. I am not sure this is right. How many comparisons are there really?</p>
  
  <pre><code>int InsertionSort(int A[], int n)
  {
     int i, j, index, counter = 0;
  
     for (i=1; i &lt; n; i++)
     {
        index = A[i];
        for (j=i-1;j &gt;= 0 &amp;&amp; A[j] &gt; index;j--)
        {
           A[j + 1] = A[j];
           counter++;
        }
        A[j+1] = index;
        counter++;
     }
     return counter;
  }
  
  int main()
  {
      int A[]= {5,4,3,2,1};
      int counter = 0;
      int n =5;
      counter = InsertionSort(A, n);
      printf("%d",counter);
  
      return 0;
  }
  </code></pre>