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


#ifndef __BIINSERTIONSORT_INC__
#define __BIINSERTIONSORT_INC__

/**

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

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

 **/


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




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



template<class T>
void BiInsertionSort<T>::biinsertionsort_1(T A[], int nSize)
{
	for(int i = 1; i < nSize; i++) 
	{
		T temp = A[i];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		
		// find place with binary search
		int low = -1;
		int high = i;
		int j; 
		while (high - low > 1) 
		{
			j = (high + low) / 2;

			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			if (temp < A[j]) 
				high = j; 
			else 
				low = j;
		}
		
		// insert
		for (j = i; j > high; j--) 
		{
			A[j] = A[j-1];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		}

		A[high] = temp;	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
	}
}



#endif