/* Function shellsort(array,n) based on Shell sort algorithm invented
   by D. L. Shell in 1959. */

#include <stdio.h>

void shellsort(int v[], int n);

main()
{
	int a[]={12,34,65,9,19,76,20,13,60,23}, n=sizeof(a)/sizeof(int), i;
        for(i=0;i<n;i++)
                printf("%d ",a[i]);
        printf("\n");
	shellsort(a,n);
        for(i=0;i<n;i++)
                printf("%d ",a[i]);
        printf("\n");
}

void shellsort(int v[], int n)
{
	int gap, i, j;
        for(gap=n/2; gap>0; gap/=2)
                for(i=0; i<n-gap; i++)
                        for(j=i; j>=0 && v[j]>v[j+gap]; j-=gap)
			{
				v[j] = v[j] + v[j+gap];
				v[j+gap] = v[j] - v[j+gap];
				v[j] = v[j] - v[j+gap];
			}
}