#include <stdio.h>
#include "ordena.h"

//----------------Algoritmo de ordenação Bubble Sort------------------//
int bubbleSort(pessoa *vetor, int tamanho){

	int  i, j = 1,n = 0, cont = 0;
	pessoa aux[1];
	while(n < tamanho && j == 1)
	{
		j = 0;
		for(i = 0; i < (tamanho - 1); i++)
		{
			cont++;
			if(vetor[i].id > vetor[i+1].id)
			{
				j = 1;
				aux[0] = vetor[i];
				vetor[i] = vetor[i+1];
				vetor[i+1] = aux[0];
			}
		}
		tamanho = tamanho -1;
	}
	return cont;
}
//-----------------------------------------------------------------------//

//----------------Algoritmo de ordenação Merge Sort----------------------//
int mergeSort (pessoa *vetor, int inicio, int fim){
		int meio;
		int x = 0, y = 0, z = 0, cont = 0;
		if (inicio < fim)
		{
			meio = (inicio + fim)/2;
			x = mergeSort (vetor, inicio, meio);
			y = mergeSort (vetor, meio + 1, fim);
			z = intercala (vetor, inicio, fim, meio);
			cont = cont + x + y + z;
		}
	return cont;
	}

int intercala(pessoa *vetor, int inicio, int fim, int meio){
	int i, cont = 0;
	int inicio_vetor1 = inicio;
	int inicio_vetor2 = meio + 1;
	int poslivre = inicio;
	pessoa aux[(fim + inicio) + 1];

	while (inicio_vetor1 <= meio && inicio_vetor2 <= fim)
	{
		cont++;
		if (vetor[inicio_vetor1].id <= vetor[inicio_vetor2].id)
		{
			aux[poslivre] = vetor[inicio_vetor1];
			inicio_vetor1 = inicio_vetor1 + 1;
		}
		else
		{
			aux[poslivre] = vetor[inicio_vetor2];
			inicio_vetor2 = inicio_vetor2 + 1;
		}
		poslivre = poslivre + 1;
	}

	//Se ainda exixtem numeros no primeiro vetor
	//que não foram intercalados
	for (i = inicio_vetor1 ; i <= meio ; i++)
	{
		aux[poslivre] = vetor[i];
		poslivre = poslivre + 1;
	}

	//Se ainda exixtem numeros no segundo vetor
	//que não foram intercalados
	for (i = inicio_vetor2 ; i <= fim ; i++)
	{
		aux[poslivre] = vetor[i];
		poslivre = poslivre + 1;
	}

	//Retorna os valores do vetor "aux" para o vetor "vetor"
	for (i = inicio ; i<=fim ; i++)
	{
		vetor[i] = aux[i];
	}
	return cont;
}
//-----------------------------------------------------------------------//

//----------------Algoritmo de ordenação Selection Sort------------------//
int selectionSort(pessoa *vetor, int tamanho){
	int i, j, cont, pos;
	pessoa eleito[1], menor[1];

	i = 0;
	j = 0;
	cont = 0;
	//Ordenando de forma crescente
	//laço que percorre da 1ª posição
	//à penúltima do vetor
	//elegendo um número para ser comparado
	for (i = 0 ; i < (tamanho - 1) ; i++)
	{
		eleito[0] = vetor[i];

		menor[0]	= vetor[i+1];	// Encontrando o menor número à direita do eleito com sua respectiva posição
		pos = i+1;					// posição do eleito = i, primeiro número à direita do
									// eleito na posição = i + 1

		for (j = i+1 ; j < tamanho  ; j++)	//Laço que percorre os elementos que estão à direita do
		{									//número eleito, retornando o menor número à direita
			cont++    ;						//e sua posição
			if (vetor[j].id < menor[0].id)
			{
				menor[0] = vetor[j];
				pos = j;
			}

		}
		cont++;
		if (menor[0].id < eleito[0].id)		//Troca do número eleito com o número da posição pos
		{									//O número da posição pos é o menor número à direita
			vetor[i] = vetor[pos];			//do número eleito
			vetor[pos] = eleito[0];
		}

	}

	return cont;
	}
//-----------------------------------------------------------------------//

//----------------Algoritmo de ordenação Quick Sort----------------------//
int quickSort (pessoa *vetor, int inicio, int fim){
	int meio, cont, x, y, z;

	cont = 0;
	if (inicio < fim)
	{
			cont++;
			meio = particao(vetor, inicio, fim);
			x = quickSort(vetor, inicio, meio);
			y = quickSort(vetor, (meio+1), fim);
			cont = cont + x + y;
	}
	return cont;
}

int particao (pessoa *vetor, int inicio, int fim){
	int i, j;
	pessoa pivo[1];

	pivo[0] = vetor[(inicio+fim)/2];
	i = inicio-1;
	j = fim+1;

	while (i < j)
	{
			do
			{
					j = j-1;
			} while (vetor[j].id > pivo[0].id);

			do
			{
				i = i+1;
			} while (vetor[i].id < pivo[0].id);

			if (i < j) troca (vetor, i, j);
	}
return j;
}

void troca (pessoa *vetor, int i, int j){
		pessoa aux[1];

		aux[0] = vetor[i];
		vetor[i] = vetor[j];
		vetor[j] = aux[0];
}
//-----------------------------------------------------------------------//

//----------------Algoritmo de ordenação Heap Sort----------------------//
void transforma_heap (int qtde){
		int i, pai, aux;

		for (i = qtde/2 ; i >= 1 ; i--)
		{
			heap_fica (i, qtde);
		}
}

void heap_fica (int i, int qtde){
		int f_esq, f_dir, maior, aux;
		maior = 1;

		if ((2*i)+1 <= qtde)
		{
				f_esq = (2*i)+1;
				f_dir = 2*i;

				if ((vetor[f_esq].id >= vetor[f_dir].id) && (vetor[f_esq].id > vetor[i].id))
					maior = i;
				else
					if ((vetor[f_dir].id > vetor[f_esq].id) && (vetor[f_dir].id > vetor[i].id))
						maior = 2*i;
		}
		else
			if (2*i <= qtde )
			{
				f_dir = 2*i;
				if (vetor[f_dir].id > vetor[i].id)
					maior = 2*i;
			}
			if (maior != i)
			{
					aux[0] = vetor[i];
					vetor[i] = vetor[maior];
					vetor[maior] = aux[0];
					heap_fica (maior, qtde);
			}
}



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