/* Programa que implementa os algoritmos de ordenacao e busca.
 * Objetivo: separar os algoritmos necessarios do programa principal de forma a organizar o codigo. 
 * Restricoes: o quicksort iterativo estah mais lento que o recursivo, acreditamos que isso deve-se
 * ao uso de uma implementacao completa da pilha.
 * Observacoes: decidimos nao utilizar o criaLog nesse arquivo devido as repeticoes exaustivas
 * durante o teste, dessa forma o log nao terah mais de 40000 linhas
 *
 * Autores: Bruno Freitas Tissei e Felipe Shi Iu Wu
 * Disciplina: Algoritmos e Estrutura de Dados II
 * Entrega: 13/12/2015 */
#include "algoritmos.h"

// troca o inteiro "a" pelo "b"
void swap(int *a, int *b) {
    int aux = *a;
    *a = *b;
    *b = aux;
}

// pesquisa binaria recursivamente em busca do elemento "elem"
// de "esq" ate "dir" em um vetor
int pesquisaBin(int vetor[], int elem, int esq, int dir) {
    int meio;
    if (esq > dir) 
        return -1;
    meio = (esq + dir) / 2;
    if (vetor[meio] == elem) 
        return meio;
    else if (elem > vetor[meio]) 
        return pesquisaBin(vetor, elem, meio + 1, dir);
    else 
        return pesquisaBin(vetor, elem, esq, meio - 1);
}

// pesquisa sequencial em busca do elemento "elem"
// em um vetor de "max" elementos
int pesquisaSeq(int vetor[], int elem, int max) {
    int i;
    for (i = 0; i < max; i++)
        if (vetor[i] == elem)
            return i;
    return -1;
}

// ordenacao usando o algoritmo SelectSort em um vetor
// de "max" elementos
void selectSort(int vetor[], int max) {
    int i, j, min, aux;
    for (i = 0; i < max - 1; i++) {
        min = i;
        for (j = i + 1; j < max; j++)
            if (vetor[j] < vetor[min])
                min = j;
        aux = vetor[min];
        vetor[min] = vetor[i];
        vetor[i] = aux;
    }
}

// ordenacao usando o algoritmo BubbleSort em um vetor
// de "max" elementos
void bubbleSort(int vetor[], int max) {
    int i, j, aux;
    for (i = 0; i < max; i++) {
        for (j = max - 1; j >= i; j--) {
            if (vetor[j] < vetor[j - 1]) {
                aux = vetor[j];
                vetor[j] = vetor[j - 1];
                vetor[j - 1] = aux;
            }
        }
    }
}

// ordenacao usando o algoritmo QuickSort Iterativo em um vetor
// que vai de "esq" ate "dir"
void quickSortI(int vetor[], int esq, int dir) {
    int e, d;
    tipoPilha pilha;

    inicPilha(&pilha);
    push(&pilha, esq, dir);
    while (!vaziaPilha(pilha)) {
        e = pilha.topo->frente->esq;
        d = pilha.topo->frente->dir;
        pop(&pilha);
        if (e < d) {
            int posPivo = particao(vetor, e, d);
            push(&pilha, e, posPivo - 1);
            push(&pilha, posPivo + 1, d);
        }
    }
}

// ordenacao usando o algoritmo QuickSort Recursivo em um vetor
// que vai de "esq" ate "dir"
void quickSortR(int vetor[], int esq, int dir) {
    if (esq < dir) {
        int posPivo = particao(vetor, esq, dir);
        quickSortR(vetor, esq, posPivo - 1);
        quickSortR(vetor, posPivo + 1, dir);
    }
}

// particao que serah utilizada no quickSortI e quickSortR
// esse algoritmo recebe um vetor e o analiza de "esq" ate "dir":
// inicialmente seleciona um pivo a partir da mediana dos elementos 
// da esquerda, direita e meio usando a formula:
// mediana = A xor B xor C xor MAX(A, B, C) xor MIN(A, B, C)
// troca o elemento da direita pelo pivo e executa a particao, mandando
// os elementos menores que o pivo para esquerda e os maiores para
// direita
// depois retorna a posicao do pivo para ser utilizado no quicksort
int particao(int vetor[], int esq, int dir) {
    int i = esq, j;
    int a = vetor[esq], b = vetor[(esq + dir) / 2], c = vetor[dir];
    // mediana entre os elementos nas posicoes esq, dir e (esq + dir) / 2
    int pivo = a ^ b ^ c ^ max(a, max(b, c)) ^ min(a, min(b,c));

    // armazena a posicao do pivo de acordo com o resultado da mediana
    int posPivo = (pivo == a) ? esq : (pivo == b) ? (esq + dir) / 2 : dir;
    swap(&vetor[posPivo], &vetor[dir]);
   
    // percorre o vetor e caso o elemento selecionado seja menor que o pivo
    // o posiciona no lugar adequado (i)
    for (j = esq; j < dir; j++)
        if (vetor[j] < pivo)
            swap(&vetor[i++], &vetor[j]);

    // coloca pivo no meio
    swap(&vetor[i], &vetor[dir]);
    return i;
}