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

/***

 Quick sort is a sequential algorithm, with an average case time of O(n log n). 

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

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

 ***/


#ifndef __QUICKSORT_INC__
#define __QUICKSORT_INC__


template <class T>
class QuickSort
{
	static int partition_1(T A[], int low, int high);
	static void quicksort_1(T A[], int low, int high);
	static void quicksort_2(T A[], int low, int high);
	static void media3(T A[], int low, int high);
	static void quicksort_3(T A[], int low, int high);
	static void quicksort_4(T A[], int low, int high);
	static void quicksort_5(T A[], int low, int high);
	static int particao_6(T A[], int low, int high);
	static void quicksort_6(T A[], int low, int high);
	static void quicksort_7(T A[], int low, int high);
	static void quicksort_9(T A[], int low, int high);
	static void quicksort_10(T A[], int low, int high);
	static void qsort_11(T* ptr_A, int number);

public:
	// pivot = A[random(low, high)]
	// partição
	static void quicksort_1(T A[], int nSize);

	// pivot = A[low]
	static void quicksort_2(T A[], int nSize);

	// pivot = media3()
	static void quicksort_3(T A[], int nSize);

	// pivot = A[high]
	static void quicksort_4(T A[], int nSize);

	// pivot = A[ (low+high)/2 ]
	static void quicksort_5(T A[], int nSize);

	// pivot = A[low]
	// partição
	static void quicksort_6(T A[], int nSize);

	// pivot = A[low]
	// poupa stack de recursividade
	static void quicksort_7(T A[], int nSize);

	// pivot = A[ (low+high)/2 ]
	// versão iterativa
	static void quicksort_8(T A[], int nSize);

	// pivot = A[ (low+high)/2 ]
	// poupa stack de recursividade
	static void quicksort_9(T A[], int nSize);

	// pivot = A[low]
	// só um ciclo na partição
	static void quicksort_10(T A[], int nSize);

	// pivot = A[rand()]
	// solução interessante
	static void quicksort_11(T* ptr_A, int nSize);
};


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


/**

  todos as variantes do algoritmo Quicksort apresentadas em seguida podem ser melhoradas
  acrescentando mais um caso terminal na recursividade:
		a ordenação de um segmento com apenas dois elementos
  para tal, deve-se acrescentar o seguinte código aos algoritmos


	// sort a two element list by swapping if necessary 
	if (low == high - 1) 
	{
		if (a[low] > a[high]) 
			troca(A[low], A[high]);
		return;
	}


 **/


/**

  todos as variantes do algoritmo Quicksort apresentadas em seguida podem ser melhoradas
  acrescentando mais um caso terminal na recursividade:
		a utilização de um algoritmo diferente (por ex., bubblesort) para segmentos de pequena dimensão
  para tal deve-se acrescentar o seguinte código aos algoritmos


	//BubbleSort if the number of elements is less than 6 
	if ((high-low) <= 6) 
	{
		//bubblesort(A, low, high);
		for (int i = high+1; i > low+1; i--)
		{
			for (int j = low; j < i-1; j++)
			{
				TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
				if (A[j] > A[j+1])
					troca(A[j], A[j+1]);
			}
		}
		return;
	}


  tipicamente "pequena dimensão" é algo inferior a 20 elementos

 **/




#include "utils.h"


template <class T>
int QuickSort<T>::partition_1(T A[], int low, int high)
{
	troca(A[low], A[random(low, high)]);
	T pivot = A[low];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
	int leftwall = low;
	for (int i = low+1; i <= high; i++)
	{
		TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		if (A[i] < pivot)
		{
			leftwall++;
			troca(A[i], A[leftwall]);
		}
	}
	troca(A[low], A[leftwall]);

	return leftwall;
}

template <class T>
void QuickSort<T>::quicksort_1(T A[], int low, int high)
{
	if (low < high)
	{
		int ploc = partition_1(A, low, high);
		quicksort_1(A, low, ploc-1);
		quicksort_1(A, ploc+1, high);
	}
}

template <class T>
void QuickSort<T>::quicksort_1(T A[], int nSize)
{
	if (nSize < 2)
		return;

	quicksort_1(A, 0, nSize-1);
}

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


template <class T>
void QuickSort<T>::quicksort_2(T A[], int low, int high)
{
	if (low >= high)
		return;
	
	int i = low;		//left-to-rigth cursor
	int j = high + 1;	//right-to-left cursor
	T pivot = A[low];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida

	//swap elements >= pivot on left side
	//swap elements <= pivot on rigth side
	while (true)
	{
		do {
			i++;
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		}while (A[i] < pivot);
		do{
			j--;
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		} while (A[j] > pivot);
		if (i >= j)
			break;
		troca(A[i], A[j]);
	}
	A[low] = A[j];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
	A[j] = pivot;	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida

	quicksort_2(A, low, j-1);
	quicksort_2(A, j+1, high);
}


template <class T>
void QuickSort<T>::quicksort_2(T A[], int nSize)
{
	if (nSize < 2)
		return;

	quicksort_2(A, 0, nSize-1);
}

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


template <class T>
void QuickSort<T>::media3(T A[], int low, int high)
{
	int meio = (low+high)/2;
	
	/**

	if (A[low] > A[meio])
		troca(A[low], A[meio]);
	if (A[low] > a[high])
		troca(A[low], A[high]);
	if (A[meio] > A[high])
		troca(A[meio], A[high]);

	 **/

	/**

	if (_X < _Y)
		return (_Y < _Z ? _Y : _X < _Z ? _Z : _X);
	else
		return (_X < _Z ? _X : _Y < _Z ? _Z : _Y);

	 **/

	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
	// verificar qual destes três valores A[low], A[meio], ou A[high]
	if (A[meio] < A[low])
	{
		TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		// A[m] < A[l]
		if (A[high] < A[meio])
			// A[h] < A[m] < A[l] 
			// A[meio] para pivot
			troca(A[low], A[meio]);
		else if (A[high] > A[low])
			// A[m] < A[l] < A[h]
			// A[low] para pivot
			;
		else
			// A[m] < A[h] < A[l]
			// A[high] para pivot
			troca(A[high], A[low]);
	}
	else
	{
		TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		// A[l] < A[m]
		if (A[high] < A[low])
			// A[h] < A[l] < A[m]
			// A[low] para pivot
			;
		else if (A[high] > A[meio])
			// A[l] < A[m] < A[h]
			// A[meio] para pivot
			troca(A[low], A[meio]);
		else
			// A[l] < A[h] < A[m]
			// A[high] para pivot
			troca(A[high], A[low]);
	}
}

template <class T>
void QuickSort<T>::quicksort_3(T A[], int low, int high)
{
	if (low >= high)
		return;
	
	int i = low;		//left-to-rigth cursor
	int j = high + 1;	//right-to-left cursor

	//igual ao quicksort_2 mas usa media3()
	media3(A, low, high);

	T pivot = A[low];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida

	//swap elements >= pivot on left side
	//swap elements <= pivot on rigth side
	while (true)
	{
		do {
			i++;
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		}while (A[i] < pivot);
		do{
			j--;
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		} while (A[j] > pivot);
		if (i >= j)
			break;
		troca(A[i], A[j]);
	}
	A[low] = A[j];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
	A[j] = pivot;	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida

	quicksort_3(A, low, j-1);
	quicksort_3(A, j+1, high);
}

template <class T>
void QuickSort<T>::quicksort_3(T A[], int nSize)
{
	if (nSize < 2)
		return;

	quicksort_3(A, 0, nSize-1);
}

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


template <class T>
void QuickSort<T>::quicksort_4(T A[], int linf, int lsup)
{
	if (lsup > linf)
	{
		int i = linf-1;
		int j = lsup;
		T pivot = A[lsup];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		while (i < j)
		{			
			while (A[++i] < pivot)
			{
				TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			}
			while ((j>=0) && (A[--j] > pivot))
			{
				TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			}
			if (i < j)
				troca(A[i], A[j]);
		}
		troca(A[i], A[lsup]);
		quicksort_4(A, linf, i-1);
		quicksort_4(A, i+1, lsup);
	}
}


template <class T>
void QuickSort<T>::quicksort_4(T A[], int nSize)
{
	if (nSize < 2)
		return;

	quicksort_4(A, 0, nSize-1);
}

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


template <class T>
void QuickSort<T>::quicksort_5(T A[], int ini,int fim)
{
	int e = ini;
	int d = fim;
	T pivot = A[ (e+d)/2 ];		TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
	while (e <= d)
	{
		while (A[e] < pivot)
		{
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			e++;
		}
		while (A[d] > pivot) 
		{
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			d--;
		}
		if (e <= d)   
		{  
			troca(A[e], A[d]);
			d--; 
			e++;
		}   
	} 
	if (d-ini > 0) 
		quicksort_5(A, ini, d);
	if (fim-e > 0) 
		quicksort_5(A, e, fim);
}


template <class T>
void QuickSort<T>::quicksort_5(T A[], int nSize)
{
	if (nSize < 2)
		return;

	quicksort_5(A, 0, nSize-1);
}


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

template <class T>
void QuickSort<T>::quicksort_6(T A[], int esq, int dir)
{
	int j;
	if (esq < dir)
	{
		j = particao_6(A, esq, dir);
		quicksort_6(A, esq, j-1);
		quicksort_6(A, j+1, dir);
	}
}

template <class T>
int QuickSort<T>::particao_6(T A[], int esq, int dir)
{
	int j = esq;
	int k = dir;
	while (j < k)
	{
		while (j < k && A[j] <= A[k])
		{
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			k--;
		}
		if (j < k)
			troca(A[j++], A[k]);
		while (A[j] < A[k])
		{
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			j++;
		}
		if (j < k)
			troca(A[j], A[k--]);
	}
	return j;
}

template <class T>
void QuickSort<T>::quicksort_6(T A[], int nSize)
{
	if (nSize < 2)
		return;

	quicksort_6(A, 0, nSize-1);
}



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


template <class T>
void QuickSort<T>::quicksort_7(T A[], int lo, int up)
{
	while (up > lo) 
	{
		int i = lo;
		int j = up;
		T pivot = A[lo];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		/*** Split in two ***/
		while (i < j) 
		{
			for ( ; A[j] > pivot; j--)
			{
				TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			}
			for (A[i] = A[j]; i < j && A[i] <= pivot; i++)
			{
				TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			}
			A[j] = A[i];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		}
		A[i] = pivot;	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		/*** Sort recursively, the smallest first ***/
		if (i-lo < up-i)
		{
			quicksort_7(A, lo, i-1);  
			lo = i+1; 
		}
		else    
		{
			quicksort_7(A, i+1, up);  
			up = i-1; 
		}
	}
}

template <class T>
void QuickSort<T>::quicksort_7(T A[], int nSize)
{
	if (nSize < 2)
		return;

	quicksort_7(A, 0, nSize-1);
}




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


//
// http://www.math.grin.edu/~wislocki/302/assignment4/quicksort.c
//

#define PUSH(pilha, l, r) {*pilha++ = (l); *pilha++ = (r);}
#define POP(pilha, l, r) {(r) = *--pilha; (l) = *--pilha;}

template <class T>
void QuickSort<T>::quicksort_8(T A[], int nSize)
{
	if (nSize < 2)
		return;

	//stack<int> s;		// A list of the ranges left to sort
	//para aumentar a rapidez de execução simula-se uma stack
	int* stk = new int[(nSize+1)*2];

	// Initially, we need to sort the whole Vector
	//s.push(0);
	//s.push(nSize-1);
	PUSH(stk, -1, -1);
	PUSH(stk, 0, nSize-1);

	//while (!s.empty()) 
	while (true)
	{
		//int right = s.top();;
		//s.pop();
		//int left = s.top();
		//s.pop();
		int left;
		int right;
		POP(stk, left, right);

		if (left == -1 && right == -1)
			break;

		if(left < right) 
		{
			//determinar pivot
			int position = (left + right) / 2;

			troca(A[left], A[position]);

			int last = left;

			for (int i = left+1; i <= right; i++)
			{
				TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
				if(A[i] < A[left]) 
				{
					last++;
					troca(A[last], A[i]);
				}
			}
			troca(A[left], A[last]);

			//s.push(left);
			//s.push(last-1);
			//s.push(last+1);
			//s.push(right);
			PUSH(stk, left, last-1);
			PUSH(stk, last+1, right);
		}
	}

	delete [] stk;
}


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

//igual ao quicksort_7() mas usa pivot central
template <class T>
void QuickSort<T>::quicksort_9(T A[], int lo, int up)
{
	while (up > lo) 
	{
		int i = lo;
		int j = up;
		T pivot = A[ (lo+up)/2 ];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		/*** Split in two ***/
		while (i < j) 
		{
			for ( ; A[j] > pivot; j--)
			{
				TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			}
			for (A[i] = A[j]; i < j && A[i] <= pivot; i++)
			{
				TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			}
			A[j] = A[i];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		}
		A[i] = pivot;	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		/*** Sort recursively, the smallest first ***/
		if (i-lo < up-i)
		{
			quicksort_9(A, lo, i-1);  
			lo = i+1; 
		}
		else    
		{
			quicksort_9(A, i+1, up);  
			up = i-1; 
		}
	}
}

template <class T>
void QuickSort<T>::quicksort_9(T A[], int nSize)
{
	if (nSize < 2)
		return;

	quicksort_9(A, 0, nSize-1);
}


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


template <class T>
void QuickSort<T>::quicksort_10(T A[], int inf, int sup)
{
	if(inf<sup)
	{
		T pivot = A[inf];
		int ant = inf;
		int i = inf+1;

		while (i <= sup)
		{
			if(A[i] < pivot)
			{
				ant++;
				troca(A[ant], A[i]);
			}
			i++;
		}

		troca(A[inf], A[ant]);

		quicksort_10(A, inf, ant-1);
		quicksort_10(A, ant+1, sup);
	}
}

template <class T>
void QuickSort<T>::quicksort_10(T A[], int nSize)
{
	if (nSize < 2)
		return;

	quicksort_10(A, 0, nSize-1);
}



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


//
// Quickly sort any number of data elements of any type into ascending order.
// By: Alex Schwendner
//
//Please see http://www.Planet-Source-Code.com/xq/ASP/txtCodeId.1098/lngWId.3/qx/vb/scripts/ShowCode.htm
//for details.

template <class T> 
void QuickSort<T>::qsort_11(T* ptr_A, int number)
{
	if(number < 1)
		return;

	// escolher pivot e outros dois elementos aleatorios
	T pivot = *(ptr_A + (rand() % (number + 1)));
	T temp1 = *(ptr_A + (rand() % (number + 1)));
	T temp2 = *(ptr_A + (rand() % (number + 1)));

	//determinar o valor "mediano" destes três elementos e usar esse como pivot
	if(pivot > temp1)
	{
		if(pivot > temp2)
		{
			if(temp1 > temp2)
				pivot = temp1;
			else
				pivot = temp2;
		}
	}
	else
	{
		if(pivot < temp2)
		{
			if(temp1 < temp2)
				pivot = temp1;
			else
				pivot = temp2;
		}
	}

	//determinar o ultimo elemento desta subsequencia
	T* next_ptr = ptr_A + number;

	//efectuar partição da subsequencia 
	//(i.e., elementos menores que pivot à esquerda, elementos maiores à direita)
	//loop é a variavel de ciclo que percorre cada elemento da subsequencia
	for(T* loop = ptr_A; loop < next_ptr; ++loop)
	{
		bool swap_bool = *loop > pivot;

		//se elemento actual menor ou igual ao pivot
		if(!swap_bool)
		{
			// se for igual tem 50% de probabilidades para ficar na partição esquerda ou direita
			if(*loop == pivot)
				swap_bool = rand() % 2 == 0;

			//se o elemento actual for menor simplesmente avança
		}

		//se elemento actual maior que pivot, procura um menor no fim da sequencia 
		//para trocar para a particao esquerda
		if(swap_bool)
		{
			//percorrer sequencia do final para o inicio
			while(next_ptr > loop)
			{
				//se encontrar um elemento menor, para
				if(*next_ptr < pivot)
					break;
				else
				{
					//se não tem valor igual ao pivot continua a procurar
					if(*next_ptr != pivot)
						--next_ptr;
					else
					{
						//se o valor é igual ao pivot tem 50% de probabiblidades de ser trocado
						if(rand() % 2 == 0)
							break;
						else
							--next_ptr;
					}
				}
			}
			troca(*loop, *next_ptr);
		}
	}

	//a particao está criada, é necessario ordenar recursivamente cada uma das particoes
	if(*next_ptr < pivot)
	{
		qsort_11(ptr_A, (next_ptr - ptr_A));
		qsort_11(next_ptr + 1, (ptr_A + number - next_ptr - 1));
	}
	else
	{
		qsort_11(ptr_A, (next_ptr - ptr_A - 1));
		qsort_11(next_ptr, (ptr_A + number - next_ptr));
	}
}


template <class T> 
void QuickSort<T>::quicksort_11(T* ptr_A, int number)
{
	if (number < 2)
		return;

	srand(number);

	qsort_11(ptr_A, number-1);
}

#endif