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


#ifndef __STOOGESORT_INC__
#define __STOOGESORT_INC__


template <class T>
class StoogeSort
{
	static void stoogesort_1(T A[], int low, int high);

public:
	static void stoogesort_1(T A[], int nSize);
};


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


template <class T>
class PermSort
{
	static bool permsort_1(T A[], int i, int nSize);

public:
	static void permsort_1(T A[], int nSize);
};



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


/**
 * A Stooge sort demonstration algorithm
 *
 * @author Patrick Morin
 */
template <class T>
void StoogeSort<T>::stoogesort_1(T A[], int lo, int hi)
{
	if(A[lo] > A[hi]) 
		troca(A[lo], A[hi]);

	if(lo + 1 >= hi)
		return;

	int third = (hi - lo + 1) / 3;
	stoogesort_1(A, lo, hi-third);
	stoogesort_1(A, lo+third, hi);
	stoogesort_1(A, lo, hi-third);
}


template <class T>
void StoogeSort<T>::stoogesort_1(T A[], int nSize)
{
	stoogesort_1(A, 0, nSize-1);
}


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


template <class T>
void BozoSort<T>::bozosort_1(T A[], int nSize)
{
	bool sorted = false;

	while (!sorted) 
	{
		int index1 = rand() % nSize;
		int index2 = rand() % nSize;  

		troca(A[index1], A[index2]);
		// Is a[] sorted?
		sorted = verifica_ordenacao(A, nSize);
	}
} 



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


/**
 * A PermSort Demonstration algorithm.  The PermSort algorithm is due
 * to Patrick Morin <http:www.scs.carleton.ca/~morin>.  The algorithm
 * works by trying every permutation until it finds one that's
 * sorted.  That's right, there are n! permutations and it takes O(n)
 * time to test each one, yielding an O(nn!) algorithm.  No hate mail
 * please.
 *	 
 * @author Patrick Morin 
 */
template <class T>
bool PermSort<T>::permsort_1(T A[], int i, int nSize)
{
	// Check if array is already sorted
	if (verifica_ordenacao(A, nSize))
	    return true;

	// Array wasn't sorted so start trying permutations until we
	// get the right one.
	for(int j = i+1; j < nSize; j++) 
	{
		troca(A[i], A[j]);

		if(permsort_1(A, i+1, nSize))
			return true;
		
		troca(A[i], A[j]);
	}
	return false;
}

template <class T>
void PermSort<T>::permsort_1(T A[], int nSize)
{
	permsort_1(A, 0, nSize);
}


#endif