/*
 * Instituto Superior de Engenharia do Porto
 *
 * Estruturas de Informação
 *
 * 2000/2001
 *
 * (C) Paulo Sousa
 *
 * ------------------------------------------
 *
 * Trabalho nº 1
 *
 *	algoritmo shellsort
 *
 */


/**

  descrição em http://www.people.fas.harvard.edu/~toub/cs50/sorting/shell.html

  Shell sort improves on the efficiency of insertion sort by quickly shifting values 
  to their destination. 
  
  best
  worst		O(n^1.5)
  expected
  average	O(n^1.25)

 **/


#ifndef __SHELLSORT_INC__
#define __SHELLSORT_INC__


template <class T>
class ShellSort
{
public:
	// metodo original
	static void shellsort_1(T A[], int nSize);

	// d = (5*d-1)/11;
	static void shellsort_2(T A[], int nSize);

	// h = 3 * h + 1;
	static void shellsort_3(T A[], int nSize);

	// incrementos variaveis
	static void shellsort_4(T A[], int nSize);

	// incrementos variaveis mas predefinidos (16)
	static void shellsort_5(T A[], int nSize);

	// metodo de Pratt
	static void shellsort_6(T A[], int nSize);

	// incrementos variaveis mas predefinidos (28)
	static void shellsort_7(T A[], int nSize);
};



//----------------------------------------------------------
//
//				I M P L E M E N T A Ç Ã O
//
//----------------------------------------------------------


/*
 * Shell Sort (original)
 *
 */
template <class T>
void ShellSort<T>::shellsort_1(T A[], int nSize)
{
	int l = 0;
	int r = nSize-1;

	for(int h = 1; h <= (r-l)/4; h = 2*h) 
		;
	for( ; h > 0; h /= 2)
		for (int i = l+h; i <= r; i++)
		{
			int j = i; 
			T v = A[i];		TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida 
			while (j >= l+h && v < A[j-h])
			{
				TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
				A[j] = A[j-h];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
				j -= h; 
			}
			A[j] = v;	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		} 
}


//
//-------------------------------------------------
//


/*
 * Shell Sort Gonnet
 *
 */
template <class T>
void ShellSort<T>::shellsort_2(T A[], int nSize)
{
	for (int d = nSize-1; d > 1; ) 
	{
		if (d < 5)  
			d = 1;
		else   
			d = (5*d-1)/11;
		/*** Do linear insertion sort in steps size d ***/
		for (int i = nSize-d; i >= 0; i--) 
		{
			T pivot = A[i];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			for (int j = i+d; j < nSize && (pivot > A[j]); j += d)
			{
				TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
				A[j-d] = A[j];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			}
			A[j-d] = pivot;	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		}
	}
}


//
//-------------------------------------------------
//


/*
 * Shell Sort Knuth
 *
 */

/*http://www.auto.tuwien.ac.at/~blieb/woop/shell.html 
 *
 * Shellsort is a simple extension of insertion sort which gains speed
 * by allowing exchanges of elements that are far apart. The idea is
 * to rearrange the array to give it the property that every hth
 * element (starting anywhere) yields a sorted array. Such an array
 * is said to be h-sorted.
 *
 * By h-sorting for some large values of h, we can move elements in
 * the array long distances and thus make it easier to h-sort for
 * smaller values of h. Using such a procedure for any sequence of
 * values h which ends in 1 will produce a sorted array.
 */
template <class T>
void ShellSort<T>::shellsort_3(T A[], int nSize)
{
	int h = 1;
	/* 
	* find the largest h value possible 
	*/
	while ((h * 3 + 1) < nSize) 
		h = 3 * h + 1;

	/* 
	* while h remains larger than 0 
	*/
	while (h > 0) 
	{
		/* 
		* for each set of elements (there are h sets)
		*/
		for (int i = h - 1; i < nSize; i++) 
		{
			/* 
			* pick the last element in the set
			*/
			T temp = A[i];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			int j = i;
			/*
			* compare the element at B to the one before it in the set
			* if they are out of order continue this loop, moving
			* elements "back" to make room for B to be inserted.
			*/
			for( j = i; (j >= h) && (A[j-h] > temp); j -= h) 
			{
				TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
				A[j] = A[j-h];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			}
			/*
			*  insert "temp" into the correct place
			*/
			A[j] = temp;	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		}
		/* 
		* all sets h-sorted, now decrease set size
		*/
		h = h / 3;
	}
}


//
//-------------------------------------------------
//



/**
 * A Shell's sort demonstration algorithm
 * ShellSortAlgorithm.java
 *
 * @author Patrick Morin
 */
template <class T>
void ShellSort<T>::shellsort_4(T A[], int nSize)
{
	for (int incr = nSize / 2; incr > 0; incr /= 2) 
	{
		for(int i = incr; i < nSize; i++) 
		{
			int j = i - incr;
			while(j >= 0) 
			{
				TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
				if (A[j] > A[j+incr]) 
				{
					troca(A[j], A[j+incr]);
					j -= incr;
				}
				else 
					j = -1;
			}
		}
	}
}




//
//-------------------------------------------------
//


/*
 *
 * Shell Sort Incerpi-Sedgewick
 *
 *
 * Robert Sedgewick
 * presented at Fourth Annual European Symposium on Algorithms
 * Barcelona, September, 1996
 *
 * http://www.cs.princeton.edu/~rs/shell/
 * http://www.cs.princeton.edu/~rs/shell/driver.c
 *
 */
template <class T>
void ShellSort<T>::shellsort_5(T A[], int nSize)
{
	int l = 0;
	int r = nSize-1;

	int incs[16] = {1391376, 463792, 198768, 86961, 33936,
					13776, 4592, 1968, 861, 336, 
					112, 48, 21, 7, 3, 1 
					};

	for (int k = 0; k < 16; k++)
	{
		int h = incs[k];
		for (int i = l+h; i <= r; i++)
		{ 
			T v = A[i];		TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			int j = i;
			while (j >= h && v < A[j-h])
			{
				TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
				A[j] = A[j-h];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
				j -= h; 
			}
			A[j] = v;	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		} 
	}
}




//
//-------------------------------------------------
//



/*
 *
 * Shell Sort Sedgewick
 *
 */
//
// não funciona pelo menos para os seguintes casos (dimensão do vector)
//		4
//
template <class T>
void ShellSort<T>::shellsort_6(T A[], int nSize)
{ 
	int l = 0;
	int r = nSize-1;

	for (int t = 1; 4*t*t <= (r-l); t += t)
		;

	for (int h = (r-l)/4; t > 0; t /= 2, h = t*t - (3*t)/2 + 1)
		for (int i = l+h; i <= r; i++)
		{ 
			T v = A[i];		TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			int j = i;
			while (j >= h && v < A[j-h])
			{ 
				TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
				A[j] = A[j-h];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
				j -= h; 
			}
			A[j] = v;	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		} 
}



//
//-------------------------------------------------
//



/*
 *
 * Shell Sort Pratt
 *
 */
template <class T>
void ShellSort<T>::shellsort_7(T A[], int nSize)
{ 
	int l = 0;
	int r = nSize-1;

	int incs[28] = {262144, 229376, 200704, 175616, 153664, 134456, 117649,
					32768, 28672, 25088, 21952, 19208, 16807,
					4096, 3584, 3136, 2744, 2401, 512, 448, 392, 343, 
					64, 56, 49, 8, 7, 1
					};

	for(int k = 0; k < 28; k++)
	{
		int h = incs[k];
		for(int i = l+h; i <= r; i++)
		{ 
			T v = A[i];		TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			int j = i;
			while (j >= h && v < A[j-h])
			{ 
				TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
				A[j] = A[j-h];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
				j -= h; 
			}
			A[j] = v;	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		} 
	}
}



#endif