CODEWITHSUNDEEP
algorithminsertion-sort
Leonardo Lopez
Leonardo Lopez

Reputation: 1143

What's the exact number of compares that it takes insertion sort to compare numbers in this array?

If I have an array A = <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.

Nevertheless, it says there are 15 comparisons. I am not sure this is right. How many comparisons are there really?

int InsertionSort(int A[], int n)
{
   int i, j, index, counter = 0;

   for (i=1; i < n; i++)
   {
      index = A[i];
      for (j=i-1;j >= 0 && A[j] > 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;
}

Upvotes: 1

Views: 19062

Answers (2)

Matt
Matt

Reputation: 2644

To me, your counter appears to be on the wrong spot. Let's say A=<3, 2>, then your algorithm would use 1 comparison, but would report counter=2. If 15 is the right answer, then this error did not occur or got canceled out somehow.

To find out if 15 really is the right answer, this is how you can improve the counter. First of all, your algorithm relies on a left-to-right evaluation order of conditions (which most programming language adhere to). What this means is that if P=false then Q is not evaluated in (P && Q). If left-to-right evaluation order is not guaranteed, then the algorithm could potentially evaluate A[-1] > index (something which would crash your program). The easiest way to count correctly is to split the conjunction of the for-loop into two separate lines as follows:

for (i=1; i < n; i++)
{
   index = A[i];
   for (j=i-1; j >= 0; j--)
   {
      // Every time this line is reached, a comparison will be performed
      counter++;
      if (A[j] > index)
      {
         A[j + 1] = A[j];
      }
   }
   A[j+1] = index;
}

If this works out, please let us know the result and please up-vote this answer.

Upvotes: 3

Guffa
Guffa

Reputation: 700552

There are 15 comparisons (and 6 swaps):

compare: 0 <= 15, 5, 1, 0, 20, 25, 30, 35, 40
compare: 0, 15 > 5, 1, 0, 20, 25, 30, 35, 40
swap:    0, 5 - 15, 1, 0, 20, 25, 30, 35, 40
compare: 0 <= 5, 15, 1, 0, 20, 25, 30, 35, 40
compare: 0, 5, 15 > 1, 0, 20, 25, 30, 35, 40
swap:    0, 5, 1 - 15, 0, 20, 25, 30, 35, 40
compare: 0, 5 > 1, 15, 0, 20, 25, 30, 35, 40
swap:    0, 1 - 5, 15, 0, 20, 25, 30, 35, 40
compare: 0 <= 1, 5, 15, 0, 20, 25, 30, 35, 40
compare: 0, 1, 5, 15 > 0, 20, 25, 30, 35, 40
swap:    0, 1, 5, 0 - 15, 20, 25, 30, 35, 40
compare: 0, 1, 5 > 0, 15, 20, 25, 30, 35, 40
swap:    0, 1, 0 - 5, 15, 20, 25, 30, 35, 40
compare: 0, 1 > 0, 5, 15, 20, 25, 30, 35, 40
swap:    0, 0 - 1, 5, 15, 20, 25, 30, 35, 40
compare: 0 <= 0, 1, 5, 15, 20, 25, 30, 35, 40
compare: 0, 0, 1, 5, 15 <= 20, 25, 30, 35, 40
compare: 0, 0, 1, 5, 15, 20 <= 25, 30, 35, 40
compare: 0, 0, 1, 5, 15, 20, 25 <= 30, 35, 40
compare: 0, 0, 1, 5, 15, 20, 25, 30 <= 35, 40
compare: 0, 0, 1, 5, 15, 20, 25, 30, 35 <= 40

Upvotes: 4

Related Questions