c++ - Insertion Sort Variation -

#include <iostream> using namespace std;   void print_array(int array[], int size) {     cout<< "insertion sort steps: ";     int j;     (j=0; j<size;j++)         cout <<" "<< array[j];     cout << endl; }  void insertion_sort(int a[], int n) {      int i;        for(int j = 1; j < n; j++) {           = 0;           while ((a[j] > a[i])) {             = i+1;           }           int m = a[j];           for(int k = 0; k <= (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; } 

i trying modify insertion sort uses linear search technique inserts jth element in correct place first comparing (j − 1)st element, (j − 2)th element if necessary, , on.

so says i = 0; should i = j-1;

my attempt:

void insertion_sort(int a[], int n) {      int i;        for(int j = 1; j < n; j++) {           = j-1;           while ((a[j] > a[i]) && (i > 0)) {             = i-1;           }           int m = a[j];           for(int k = (j-i-1); k >= 0; k--) {             a[j-k] = a[j-k-1];            }           a[i] = m;           print_array(a,n);        } } 

here output

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 

the first step works correct 2nd step when starts fail.

the

          while ((a[j] > a[i]) && (i > 0)) {             = i-1;           } 

is wrong, because causes insertion of a[j] @ index 0 if a[j] not moved. change to

          while (0 <= && a[j] < a[i]) --i;           ++i; 

also, shifting loop wrong , complicated - change to

          int m = a[j];           (int k = j; k > i; k--) a[k] = a[k-1];           a[i] = m;