j=2 or j=1? of insertion sort with sentinel?

j=2.  You can also run with j=1.  The logic is exactly the same as a simple straight insertion sort.  In that case though you will run an extra loop.  The improved version can be found in Listing 1. 

Listing 1:

#include <stdio.h>
#include <limits.h>
#define N 11
int main(int c,char *v[])
{
  int A[N]={-INT_MAX,1,5,6,9,1,3,0,-2,-10,7};
  int i,j,k;
  for(j=2;j<N;j++){
    k=A[j];
    i=j-1;
    while(A[i]>k)
      A[i+1]=A[i--];
    A[i+1]=k;
  }
  for(i=1;i<N;i++)
    printf("%d ",A[i]);
  printf("\n");
  return 0;
}

Daily Practice 20110504

Insertion Sort 63 (C): Good

Insertion Sort w Sentinel 3 (C): Good

Selection Sort 25 (C): Good

 

Insertion sort with sentinels 1 and 2

Insertion sort w sentinel 1 : Bad

Insertion sort w sentinel 2 : Good

1 was wrong because I misspelled INT_MAX and used MAX_INT instead. Shame. I looked that up before I started.

This is the implementation which I settled on 2. In practice, having a sentinel could really be hard. 

#include <stdio.h>
#include <limits.h>
#define N 11
int main (int c, char *v[])
{
  int A[N] = { -INT_MAX,10,1,7,4,3,12,8,9,6,0};
  int i,j,k;
  for(j=1;j<N;j++){
    k=A[j];
    i=j-1;
    while(A[i]>k)
      A[i+1]=A[i--];
    A[i+1]=k;
  }
  for(i=1;i<N;i++)
    printf("%d ",A[i]);
  printf("\n");
  return 0;
}