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