// Shellsort for a table of integers
#include <stdio.h>
#include <stdlib.h>

void shellsort(int *a,int n) 
{
int group;
int i,j,h,hWork;
int v;
for (h=1;
     (hWork=3*h+1)<n;
     h=hWork)
  ;
printf("First h will be %d\n",h);

printf("Unsorted input\n");
for (i=0;i<n;i++)
  printf("%3d %3d\n",i,a[i]);

for ( ;h>0;h/=3)
{
  for (group=0; group<h; group++)
    for (i=group+h; i<n; i+=h)
    {
      v=a[i];
      j=i;
      while (j>=h && a[j-h]>v)
      {    
        a[j]=a[j-h];
        j -= h;
      }
      a[j]=v;
    }
  printf("after h=%d\n",h);
  for (i=0;i<n;i++)
    printf("%3d %3d %3d\n",i,a[i],i%h);
}
}

main()
{
int *arr;
int i,arrSize;
int seed;

printf("enter number of keys\n");
scanf("%d",&arrSize);
arr=(int*) malloc(sizeof(int)*arrSize);
if (!arr)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}
printf("enter seed\n");
scanf("%d",&seed);
srandom(seed);
for (i=0;i<arrSize;i++)
  arr[i]=abs(random()%100);
shellsort(arr,arrSize);
}