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


/**

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

 **/


#ifndef __BI_BUBBLESORT_INC__
#define __BI_BUBBLESORT_INC__


template <class T>
class BiBubbleSort
{
public:
	static void bibubblesort_1(T A[], int nSize);
};



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



template <class T>
void BiBubbleSort<T>::bibubblesort_1(T A[], int nSize)
{
	int j;
	int limit = nSize;
	int st = -1;
	while (st < limit) 
	{
		bool flipped = false;
		st++;
		limit--;
		for (j = st; j < limit; j++) 
		{
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			if (A[j] > A[j + 1]) 
			{
				troca(A[j], A[j+1]);
				flipped = true;
			}
		}
		if (!flipped) 
			return;

		for (j = limit; --j >= st;) 
		{
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			if (A[j] > A[j + 1])
			{
				troca(A[j], A[j+1]);
				flipped = true;
			}
		}
		if (!flipped)
			return;
	}
}


#endif