Best case , Worst case , Random data input for insertion sort algorithm?

Question

This is the code I wrote for inputting random numbers initially and then sorting them with the insertion sort method.

        #include<iostream>

        #include <cstdlib>

        #include <ctime>

        using namespace std;

        int main(void)
        {

           int array[10];

           srand (time(0));

           for (int i = 0; i < sizeof(array)/sizeof(array[0]); i++ )// inputting values into array[10]
           {
              array[i] = 1 + (rand()%100); //any random number between 1 - 100
           }
           cout <<" Before sorting " << " ---" <<endl;
           for (int i = 0; i < sizeof(array)/sizeof(array[0]); i++ )// printing the values
           {
               cout  <<  array[i]<< endl;
           }


           int key ;
           int t;//for future purpose
           int compcount = 0;//to keep track of comparisons
           for (int j = 1; j<sizeof(array)/sizeof(array[0]);j++)
           {
               key = array[j];//assign to second element initially
               t = j-1;//assign to first element initially
               while (j > 0 && array[t]>key)
               {
                   array[t+1] = array[t];//moving array if bigger than next element
                   t = t-1;
                   compcount++;
               }
               array[t+1] = key;
           }
           cout << " After sorting" << " --- " <<endl;

           for (int i = 0; i < sizeof(array)/sizeof(array[0]); i++ )
           {
               cout  <<  array[i]<< endl;
           }
           cout << "comparison count is " << compcount << endl;
           system ("pause");

           return 0;

        }

I'll be honest , I have a project and it asks to run the algorithm for the best , worst and random input and calculate the number of key comparisons (Which I believe is "compcount" in this code)

Now random input would make sense for this. When I did another code with "an already sorted "array of numbers (the best case scenario) ,the number of key comparisons was 0. Can someone shed some light onto whether the worst case scenario is just the complete opposite of that? If that were the case I tried doing that but I only got 32 comparisons with the size of the array being 32.

Sorry for the long question . Worst case input should have (n^2-n)/2 number of comparisons right? And the best case should have n-1 because only the first element would run through the entire list and confirm it being sorted.How do I get this in code?

Answer 1

There's one error in your program

           while (j > 0 && array[t]>key)

should be

           while (t >= 0 && array[t]>key)

Other than that, it works for me with the inverse sorted input. It is indeed the worst case and the result clearly shows it.

You've got the result off by n-1, but that's a minor problem. For a solution, see @Mranz's answer.

Answer 2

You are making a comparison as part of the while conditional, which means you are only counting a successful comparison, which is why your best case result is wrong. compcount++ should also be right above the while loop.

Edit:

compCount++;
while (t >= 0 && array[t] > key)
{
    array[t+1] = array[t];//moving array if bigger than next element
    t = t-1;

    if (t >= 0) // This is a hack to ensure that 't >= 0' will pass
       compCount++; // and another comparison will happen
}