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


#ifndef __INSERTIONSORT_INC__
#define __INSERTIONSORT_INC__

/**

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

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

 **/


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




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



template<class T>
void InsertionSort<T>::insertionsort_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
		for (int j = i-1; j >= 0 && temp < A[j]; j--)
		{
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			A[j+1] = A[j];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		}
		A[j+1] = temp;	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
	}
}



#endif