### Insertion Sort Algorithm with comparison counter

So I have an insertion sort function implemented that sorts through an array, but I'm having a problem showing the correct number of comparisons to work.
Each time I'm checking a value with another, the counter should update.
For instance, having an array of 10 elements going from 10-1 should give 45 comparisons, but I'm getting 54 comparisons.

 ``12345678910111213141516`` ``````void insertionSort(int a[], int& comparisons, const int& numOfElements) { int j, value; for (int i = 1; i < numOfElements; i++) { value = a[i]; for (j = i - 1; j >= 0 && a[j] > value; j--) { a[j + 1] = a[j]; comparisons++; } comparisons++; a[j + 1] = value; } }``````
Last edited on
Why would it be 45 comparisons? You have 11 values.

0 1 2 3 4 5 6 7 8 9 10

COmpare 1 to 1, 1-2-1-3 1-4 1-5 1-6 1-7 1-8 1-9 1-10

Do this for each value.

10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 55

That is if you have 11 elements. In your array you say you have 10 elements, but then say your index is from 0-10, which is actually 11 elements.

If you actually have 10 elements, it becomes

9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45
Last edited on
oh my bad it's 10-1. But anyways the way I'm still making the comparisons is still wrong that's more important.
 ``12345678910`` `````` for (int i = 1; i < numOfElements; i++) { for(int k=i+1;k<=numOfElements;k++) { comparisons++; } } ``````

I know this works for 10 elements. Im not really sure what you are trying to accomplish with your for loop.
Topic archived. No new replies allowed.