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


//
// este é um algoritmo "desenhado" para máquinas paralelas, 
// com fraco desempenho em máquinas sequencias (semelhante ao bubblesort)
//

/***

 Odd-Even sort is a parallel algorithm, with an worst case time of O(n), 
 running on n processors. Its absolute speed up is O(log n), so its efficiency is O((log n)/n). 

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

 ***/


#ifndef __ODDEVENSORT_INC__
#define __ODDEVENSORT_INC__


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



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



/**
 * An Odd-Even Transposition sort demonstration algorithm
 *
 * @author Andrew Kitchen
 * @version 	22 Nov 1995
 *
 *
 * http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html
 *
 */
//
// não funciona pelo menos para os seguintes casos (dimensão do vector)
//		5
//
template <class T>
void OddEvenSort<T>::oddevensort_1(T A[], int nSize)
{
	for (int i = 0; i < nSize/2; i++ ) 
	{
		for (int j = 0; j+1 < nSize; j += 2) 
		{
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		    if (A[j] > A[j+1])
				troca(A[j], A[j+1]);
		}
		for (j = 1; j+1 < nSize; j += 2) 
		{
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		    if (A[j] > A[j+1]) 
				troca(A[j], A[j+1]);
		}
	}	
}




#endif