shell.cpp

#include <iostream>
#include <cstdlib>
#include <math.h>

using namespace std;

void vstavka(int *arrayPtr, int length) // ?????????? ?????????
{
    int temp, // ????????? ?????????? ??? ???????? ???????? ???????? ???????????? ???????
        item; // ?????? ??????????? ????????
    for (int counter = 1; counter < length; counter++)
    {
        temp = arrayPtr[counter]; // ?????????????? ????????? ?????????? ??????? ????????? ???????? ???????
        item = counter-1; // ?????????? ?????? ??????????? ???????? ???????
        while(item >= 0 && arrayPtr[item] > temp) // ???? ?????? ?? ????? 0 ? ?????????? ??????? ??????? ?????? ????????
        {
            arrayPtr[item + 1] = arrayPtr[item]; // ???????????? ????????? ???????
            arrayPtr[item] = temp;
            item--;
        }
    }
}

int		fibonacci(int number)
{
	if (number == 0 || number == 1)
		return (1);
	return (fibonacci(number - 1) + fibonacci(number - 2));
}

int nextstep(int prev)
{
	int b = prev;
	double i = b / 2;
//	cout << b << i << endl;
	while (i / b > 1.35)
	{
		b = b - 1;
		cout << "smth" << endl;
	}
	return (b);
}

int getj(int step)
{
	return (pow(3, step) - 1 / 2);
}

int getbigj(int n)
{
	for (int i = 0; i < n; i++)
	{
		if ((pow(3, i) - 1) / 2 > n)
			return (i - 1); 
	}
}

int main()
{
	int i, j, step;
	int count = 0;
	int n;
	cin >> n;
	int *mass = new int[n];
	int copies = 0;
	int compare = 0;
	int veryj = getbigj(n);
	//for (i = n - 1; i >= 0; i--)
	//	mass[n - i - 1] = i;
	for (i = 0; i < n; i++)
		mass[i] = rand();
	cout << "not sorted massive" << endl;
//	for (i = 0; i < n; i++)
//		cout << mass[i] << endl;
//	cout << "~~~~~~~~~~~~~~~~~~" << endl;
	int tmp;
	for (step = getj(veryj); step > 0; step = getj(veryj - ++count), compare++)
	{
		cout << "step   " << step << endl;
		for (i = step; i < n && compare++; i++)
		{
		    tmp = mass[i];
		    copies++;
		    for (j = i; j >= step; j -= step, compare++)
		    {
		    	
		        if (tmp < mass[j - step] && copies++ && compare++)
		            mass[j] = mass[j - step];
		        else
		            break;
		    }
		    mass[j] = tmp;
		    copies++;
		}
	}
	for (int i = 0; i < n; i++)
		cout << i <<"    " <<mass[i] << endl;
	cout << copies << "    " << compare << endl;
	delete[] mass;
	return (0);
}