title: Best case , Worst case , Random data input for insertion sort algorithm?
body: <p>This is the code I wrote for inputting random numbers initially and then sorting them with the insertion sort method.</p>
  
  <pre><code>        #include&lt;iostream&gt;
  
          #include &lt;cstdlib&gt;
  
          #include &lt;ctime&gt;
  
          using namespace std;
  
          int main(void)
          {
  
             int array[10];
  
             srand (time(0));
  
             for (int i = 0; i &lt; sizeof(array)/sizeof(array[0]); i++ )// inputting values into array[10]
             {
                array[i] = 1 + (rand()%100); //any random number between 1 - 100
             }
             cout &lt;&lt;" Before sorting " &lt;&lt; " ---" &lt;&lt;endl;
             for (int i = 0; i &lt; sizeof(array)/sizeof(array[0]); i++ )// printing the values
             {
                 cout  &lt;&lt;  array[i]&lt;&lt; endl;
             }
  
  
             int key ;
             int t;//for future purpose
             int compcount = 0;//to keep track of comparisons
             for (int j = 1; j&lt;sizeof(array)/sizeof(array[0]);j++)
             {
                 key = array[j];//assign to second element initially
                 t = j-1;//assign to first element initially
                 while (j &gt; 0 &amp;&amp; array[t]&gt;key)
                 {
                     array[t+1] = array[t];//moving array if bigger than next element
                     t = t-1;
                     compcount++;
                 }
                 array[t+1] = key;
             }
             cout &lt;&lt; " After sorting" &lt;&lt; " --- " &lt;&lt;endl;
  
             for (int i = 0; i &lt; sizeof(array)/sizeof(array[0]); i++ )
             {
                 cout  &lt;&lt;  array[i]&lt;&lt; endl;
             }
             cout &lt;&lt; "comparison count is " &lt;&lt; compcount &lt;&lt; endl;
             system ("pause");
  
             return 0;
  
          }
  </code></pre>
  
  <p>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)</p>
  
  <p>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.</p>
  
  <p>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?</p>