Shortcut for chapter specific information

Tuesday, May 3, 2011

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;
}

No comments:

Post a Comment