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


/**

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

  best		O(n^2)
  worst		O(n^2)
  expected	O(n^2)

  **/


#ifndef __SHAKERSORT_INC__
#define __SHAKERSORT_INC__


template <class T>
class ShakerSort
{
public:
	static void shakersort_1(T A[], int nSize);

	static void shakersort_2(T A[], int nSize);

	static void shakersort_3(T A[], int nSize);
};



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



template <class T>
void ShakerSort<T>::shakersort_1(T A[], int nSize)
{
	int i = 0;
	int k = nSize - 1;

	while (i < k) 
	{
		int min = i;
		int max = i;
		for (int j = i + 1; j <= k; j++) 
		{
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			if (A[j] < A[min]) 
				min = j;
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			if (A[j] > A[max]) 
				max = j;
		}
		troca(A[min], A[i]);
		if (max == i) 
			troca(A[min], A[k]);
		else 
			troca(A[max], A[k]);
		i++;
		k--;
	}
}


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


/**
 * A shaker sort demonstration algorithm
 * @author Patrick Morin
 */
template <class T>
void ShakerSort<T>::shakersort_2(T A[], int nSize)
{
	for(int m = nSize/2; m > 0; m /= 2) 
	{
		for(int i = 0; i < nSize - m; i++) 
		{
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			if(A[i] > A[i+m]) 
				troca(A[i], A[i+m]);
		}
	}
	bool changed;
	do {
		changed = false;
		for (int j = 0; j < nSize-1; j++) 
		{
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			if (A[j] > A[j+1]) 
			{
				troca(A[j], A[j+1]);
				changed = true;
			}
		} 
	} while (changed);
}



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


/**
 * A shaker sort 2 demonstration algorithm. O(nlg^2n)
 * @author Patrick Morin
 */
template <class T>
void ShakerSort<T>::shakersort_3(T A[], int nSize)
{
	for(int n = nSize/2; n > 0; n /= 2) 
	{
		for(int m = n; m > 0; m /= 2) 
		{
			for(int i = 0; i < nSize - m; i++) 
			{
				TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
				if(A[i] > A[i+m]) 
					troca(A[i], A[i+m]);
			}
		}
	}
	bool change;
	do {
		change = false;
		for (int j = 0; j < nSize-1; j++) 
		{
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			if (A[j] > A[j+1]) 
			{
				troca(A[j], A[j+1]);
				change = true;
			}
		} 
	} while(change);
}



#endif