#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 100 //кол-во эл-в массива
void sort (long *x, long n); // прототип функции сортировки методом Шелла

int main ()
{
	long x[N];  // обьявление массива x[N]
	int i;
	srand((unsigned int)time(0));
	printf ("\n Vyvod massiva: \n");
	for (i=0;i<N;i++)
	{
		x[i]=rand()%100; //массив заполняется случ. Числами (до 99)
		printf("%5d",x[i]);
	}
	sort (x,N);
	system("PAUSE");
}

void sort(long* x,long n )
{
	int i,k,tmp,c,m;
	c=0; m=0;    // Переменные для подсчета кол-ва сравнений и пересылок между элементами
	int incr=n/2;    
	while (incr>0)
	{
		for (i=incr; i<n; i++)
		{
			k=i-incr;
			while (k>=0)
			{
				c++;
				if (x[k]>x[k+incr])
				{
					tmp=x[k]; x[k]=x[k+incr]; x[k+incr]=tmp;
					m++; k=k-incr;
				}
				else k=-1;
			}
		}
		incr=incr/2;
	}

	printf ("\n\n Sortirovka metodom Shella: \n");
	for (i=0; i<n; i++)
		printf("%5ld", x[i]);
	printf ("\n\n Kolichestvo sravneniy = %d", c);
	printf ("\n kolichestvo peresylok = %d", m);
}

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <string>

template<class _Ty,size_t _Dim>
void shellSort(_Ty (&array)[_Dim])
{
	size_t inc=_Dim;
	while(inc>>=1)
	{
		for(size_t i=inc;i<_Dim;++i)
		{
			_Ty tmp=array[i];
			size_t j=i;
			while(j>=inc && array[j-inc]>tmp)
			{
				array[j]=array[j-inc];
				j-=inc;
			}
			array[j]=tmp;
		}
	}
}

template<class _Ty,size_t _Dim>
void printArray(std::string msg,_Ty (&array)[_Dim])
{
	std::cout<<msg<<std::endl;
	for(size_t i=0;i<_Dim;++i)
	{
		std::cout<<array[i]<<' ';
	}
	std::cout<<std::endl;
}

const size_t N=100;

int main ()
{
	setlocale(LC_ALL,"russian_russia");
	srand(static_cast<unsigned int>(time(0)));

	long x[N];  
	for (size_t i=0;i<N;++i)
	{
		x[i]=rand()%100; 
	}

	printArray("Исходный массив:",x);
	shellSort(x);
	printArray("Отсортированный массив:",x);

	system("PAUSE");
}

main(){}