#include<stdio.h>
#include<stdlib.h>
#include<math.h>


void p(int v[],int n)
{
	int i=n;
	while(i>0)
	{
		printf("v[%d]=%d\n",n-i,v[n-i]);
		i--;
	}
}

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

main()
{
	int *v,n;
	printf("How many elements? ");
	scanf("%d",&n);
	getchar();
	
	v=(int*)malloc(n*sizeof(int));
	int i;
	
	for(i=0;i<n;i++)
	{
		v[i]=rand()%(int)pow(n,2);//[0,n^2]
	}
	printf("\n\nbefore shellsort:\n");
	p(v,n);
	shellsort(v,n);
	printf("\nafter shellsort:\n");
	p(v,n);
}