#include <stdio.h>
#include <stdlib.h>

#define VECTOR_SIZE 100000

long fatorial (int n) {
    if (n > 1) 
        return n * fatorial (n - 1);
    return 1;
}

long fib(int n) {
    if (n <= 1) return 1;
    return fib(n - 1) + fib (n - 2);
}

int busca(int vet[], int ini, int fim, int n) {
    if (ini >= fim) return -1;
    if (vet[ini] == n) return ini;
    return busca(vet, ini + 1, fim, n);
}

int buscaBinaria (int vet[], int ini, int fim, int n) {
    int meio;
    if (fim == ini) return -1;
    meio = ini + ((fim - ini) / 2);
    if (vet[meio] == n) return meio;
    if (vet[meio] > n)
        return buscaBinaria(vet, ini, meio, n);
    return buscaBinaria(vet, meio + 1, fim, n);
}

long potRec (long a, int b) {
    if (b == 0) return 1;
    return a * potRec(a, b - 1);    
}

long potRec2 (long a, int b) {
    long tmp;
    if (b == 0) return 1;
    if (b % 2 == 0) {
        tmp = potRec2(a, b / 2);
        return  tmp * tmp;
    } else {
        tmp = potRec2(a, (b - 1) /2);
        return tmp * tmp * a;
    }
}

long potIte(long a, int b) {
   long res = 1;
   int i;
   for (i = 0; i < b; i++)
    res *= a;
   return res;
}


int seleciona (int v[], int res[], int ini, int fim, int pivot, int maior) {
    int ret = 0;
    int i;
    for (i = ini; i < fim; i++) {
        if (maior == 1) {
            if (v[i] > pivot) {
                res[ret] = v[i];
                ret++;
            }
        } else {
            if (v[i] <= pivot) {
                res[ret] = v[i];
                ret++;
            }
        }        
    }
    return ret;
}

void quicksort (int v[], int ini, int fim) {
    int pivot;
    int *menores, *maiores;
    int qtdMenores, qtdMaiores;
    int i;
    
    if (ini + 1 >= fim) return;
    pivot = v[ini];
    menores = malloc (sizeof(int) * (fim - ini));
    maiores = malloc (sizeof(int) * (fim - ini));
    
    qtdMenores = seleciona(v, menores, ini + 1, fim, pivot, 0);
    qtdMaiores = seleciona(v, maiores, ini + 1, fim, pivot, 1);
    
    quicksort(menores, 0, qtdMenores);
    quicksort(maiores, 0, qtdMaiores);
    
    for (i = 0; i < qtdMenores; i++)
        v[ini + i] = menores[i];
    v[qtdMenores] = pivot;
    for (i = 0; i < qtdMaiores; i++) 
        v[qtdMenores + 1 + i] = maiores [i];
        
    
    free(menores);
    free(maiores);
    
}

int main (int argc, char *argv[]) {
    int i;
    int *vet = malloc(sizeof(int) * VECTOR_SIZE);
    
    printf("Fat:\n");
    for (i = 0; i < 20; i++)
        printf("%ld\n", fatorial(i));

    printf("Fib:\n");
    for (i = 0; i < 20; i++)
        printf("%ld\n",fib(i));
        
    printf("\n\nPot 42^43: PotRec %li PotRec2 %li PotIte %li\n", potRec(42, 43), potRec2(42, 43), potIte(42, 43));
    
    srand(42);//inicializa o gerador de numeros aleatorios
    for (i = 0; i < VECTOR_SIZE; i++)
        vet[i] = rand();

    printf("\n\nBusca: tem 1008477284? Busca: %d \n", busca(vet, 0, VECTOR_SIZE, 1008477284));
    
    printf("Ordenando...");
    quicksort (vet, 0, VECTOR_SIZE);
    
    for (i = 1; i < VECTOR_SIZE; i++) {
        if (vet[i - 1] > vet[i])
            printf("O vetor deveria ter sido ordenado\n");
    }
    printf("OK\n");
    fflush(stdout);
    
    printf("\n\nBusca depois de ordenado tem 1008477284? Busca: %d Busca Binaria %d \n", busca(vet, 0, VECTOR_SIZE, 1008477284), buscaBinaria(vet, 0, VECTOR_SIZE, 1008477284));
    printf("\n\nBusca depois de ordenado tem 42? Busca: %d Busca Binaria %d \n", busca(vet, 0, VECTOR_SIZE, 42), buscaBinaria(vet, 0, VECTOR_SIZE, 42));
            
    free(vet);
    return 0;
}