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


/**

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

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

 **/


#ifndef __SELECTIONSORT_INC__
#define __SELECTIONSORT_INC__


template<class T>
class SelectionSort
{
	static T maximo(const T A[], int n);

public:
	//normal
	static void selectionsort_1(T A[], int nSize);

	//com flag
	static void selectionsort_2(T A[], int nSize);
};



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


template<class T>
T SelectionSort<T>::maximo(const T A[], int n)
{
	int pos = 0;
	for(int i = 1; i < n; i++)
	{
		TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		if (A[i] > A[pos])
			pos  = i;
	}
	return pos;
}


template<class T>
void SelectionSort<T>::selectionsort_1(T A[], int nSize)
{
	for (int n = nSize; n > 1; n--)
	{
		int j = maximo(A, n);
		troca(A[j], A[n - 1]);
	}
}


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

template<class T>
void SelectionSort<T>::selectionsort_2(T A[], int nSize)
{
	bool sorted = false;
	for (int n = nSize; !sorted && (n > 1); n--) 
	{
		int pos = 0;
		sorted = true;
		// find largest
		for (int i = 1; i < n; i++)
		{
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			if (A[pos] <= A[i]) 
				pos = i;
			else 
				sorted = false; // out of order
		}
		troca(A[pos], A[n - 1]);
	}
}

#endif