//
//Author:  SUZUKI, RICARDO

// Shell Sort program
// last update on Friday, April 25

#include<iostream>
#include<cstdlib>
#include<fstream>
#include<iomanip>

using namespace std;

int Many_int();
//PRECONDITION: there must be a .txt file with int
//POSTCONDITIN: returns the amount of int in the file

void fill_up_array(int array[]);
//PRECONDITION: receives an array
//POSTCONDITIN: fill it up with the numbers from
//			the .txt file

void Shell_Sort(int array[], int );
//PRECONDITION: receives the array and its size
//POSTCONDITIN: sorts the array

void Print(int array[], int size);
//PRECONDITION: receives an array and its size
//POSTCONDITIN: prints the array to a file


void main(void)
{
	int dummy=0;
	int	many_numbers =Many_int();
	
	int *array_to_shell;
	array_to_shell = new int[many_numbers];

	fill_up_array(array_to_shell);

	// call the sort function
	Shell_Sort(array_to_shell, many_numbers);
	
	Print(array_to_shell, many_numbers);
}

void Print(int array[], int size)
{
	ofstream outfile;
	outfile.open("output.txt");

	outfile<<"********* Shell Sort *********** "<<endl;
	for( int i=0; i< size ; i++)
	{
		outfile<< setw(10)<<array[i]<<endl;
	}
	
}

//*************** S H E L L  S O R T *****************
void Shell_Sort(int array[], int MAXSIZE)
{
	int i=0;
	int j=0;
	int h=1;
	int v=0;
	
	do
	h = 3*h+1;
	while (h <= MAXSIZE);
	
	do {
		h /= 3;
		for (i=h+1; i<= MAXSIZE; i++) 
		{
			v = array[i];
			j = i;
			while ((j>h) && (array[j-h] > v))
			{
				array[j] = array[j-h];
				j -= h;
			}
			array[j] = v;
		}
	} while (h > 1);
}


// get integers from file and put in array
void fill_up_array(int array[])
{
	int dummy;
	int i=0;
	ifstream fill_array;
	fill_array.open("input.txt");
	
	while(!fill_array.eof())
	{
		fill_array>>dummy;
		array[i] = dummy;
		i++;
	}
	
	fill_array.close();	
}

// counts how many numbers in the file
int Many_int()
{
	ifstream count_file;
	count_file.open("input.txt");
	if(!count_file)
	{
		cout<<"There is no file to read"<<endl;
		return EXIT_FAILURE;
	}
	
	int many_numbers=0;
	int dummy;
	
	while(!count_file.eof())
	{
		count_file>>dummy;
		many_numbers++;	
	}
	--many_numbers;
	count_file.close();
	return many_numbers;
}