title: Insertion Sort Variation
body: <pre><code>#include &lt;iostream&gt;
  using namespace std;
  
  
  void print_array(int array[], int size)
  {
      cout&lt;&lt; "insertion sort steps: ";
      int j;
      for (j=0; j&lt;size;j++)
          cout &lt;&lt;" "&lt;&lt; array[j];
      cout &lt;&lt; endl;
  }
  
  void insertion_sort(int a[], int n)
  {
  
      int i;
         for(int j = 1; j &lt; n; j++) {
            i = 0;
            while ((a[j] &gt; a[i])) {
              i = i+1;
            }
            int m = a[j];
            for(int k = 0; k &lt;= (j-i-1); k++) {
              a[j-k] = a[j-k-1];
  
            }
            a[i] = m;
            print_array(a,n);
         }
  }
  
  int main() {
      int array[6]= {3,2,4,5,1,6};
      insertion_sort(array,6);
      return 0;
  }
  </code></pre>
  
  <p>I am trying to modify this the insertion sort that it uses a linear search technique that inserts the jth element in the correct place by first comparing it with the (j − 1)st element, then the (j − 2)th element if necessary, and so on.</p>
  
  <p>So where it says <code>i = 0;</code> it should now be <code>i = j-1;</code></p>
  
  <p>My attempt:</p>
  
  <pre><code>void insertion_sort(int a[], int n)
  {
  
      int i;
         for(int j = 1; j &lt; n; j++) {
            i = j-1;
            while ((a[j] &gt; a[i]) &amp;&amp; (i &gt; 0)) {
              i = i-1;
            }
            int m = a[j];
            for(int k = (j-i-1); k &gt;= 0; k--) {
              a[j-k] = a[j-k-1];
  
            }
            a[i] = m;
            print_array(a,n);
         }
  }
  </code></pre>
  
  <p>Here is the output</p>
  
  <pre><code>insertion sort steps:  2 3 4 5 1 6
  insertion sort steps:  4 2 2 5 1 6
  insertion sort steps:  5 4 4 4 1 6
  insertion sort steps:  5 4 4 1 4 6
  insertion sort steps:  6 5 5 5 5 5
  </code></pre>
  
  <p>The first step is works correct by the 2nd step is when it all starts to fail.</p>