/**
 * PHM Open Source — Módulo 08: Algoritmos de Ordenação & Busca em C
 * Implementação comentada de Bubble Sort, Selection Sort, Insertion Sort, Quick Sort e Busca Binária
 * Prof. Paulo Henrique Maciel · PHM Tech
 */

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

void trocar(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void exibir_vetor(int v[], int n, const char *rotulo) {
    printf("%-20s: [ ", rotulo);
    for (int i = 0; i < n; i++) {
        printf("%d%s", v[i], (i < n - 1) ? ", " : " ");
    }
    printf("]\n");
}

// 1. Bubble Sort (Ordenação por Flutuação/Bolha) - O(n²)
void bubble_sort(int v[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (v[j] > v[j + 1]) {
                trocar(&v[j], &v[j + 1]);
            }
        }
    }
}

// 2. Selection Sort (Ordenação por Seleção) - O(n²)
void selection_sort(int v[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (v[j] < v[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            trocar(&v[i], &v[min_idx]);
        }
    }
}

// 3. Insertion Sort (Ordenação por Inserção) - O(n²)
void insertion_sort(int v[], int n) {
    for (int i = 1; i < n; i++) {
        int chave = v[i];
        int j = i - 1;
        while (j >= 0 && v[j] > chave) {
            v[j + 1] = v[j];
            j--;
        }
        v[j + 1] = chave;
    }
}

// 4. Quick Sort (Divisão e Conquista) - O(n log n)
int particionar(int v[], int baixo, int alto) {
    int pivo = v[alto];
    int i = (baixo - 1);
    for (int j = baixo; j < alto; j++) {
        if (v[j] < pivo) {
            i++;
            trocar(&v[i], &v[j]);
        }
    }
    trocar(&v[i + 1], &v[alto]);
    return (i + 1);
}

void quick_sort(int v[], int baixo, int alto) {
    if (baixo < alto) {
        int pi = particionar(v, baixo, alto);
        quick_sort(v, baixo, pi - 1);
        quick_sort(v, pi + 1, alto);
    }
}

// 5. Busca Binária (Requer vetor previamente ordenado) - O(log n)
int busca_binaria(int v[], int n, int alvo) {
    int inicio = 0;
    int fim = n - 1;
    while (inicio <= fim) {
        int meio = inicio + (fim - inicio) / 2;
        if (v[meio] == alvo) return meio; // Encontrado no índice 'meio'
        if (v[meio] < alvo) inicio = meio + 1;
        else fim = meio - 1;
    }
    return -1; // Não encontrado
}

int main(void) {
    printf("====================================================================\n");
    printf("  PHM OPEN SOURCE — DEMONSTRACAO DE ALGORITMOS DE ORDENACAO & BUSCA\n");
    printf("====================================================================\n\n");

    int original[] = { 64, 34, 25, 12, 22, 11, 90, 88, 45, 5 };
    int n = sizeof(original) / sizeof(original[0]);
    int v[10];

    // Teste 1: Bubble Sort
    for (int i = 0; i < n; i++) v[i] = original[i];
    bubble_sort(v, n);
    exibir_vetor(v, n, "Bubble Sort");

    // Teste 2: Selection Sort
    for (int i = 0; i < n; i++) v[i] = original[i];
    selection_sort(v, n);
    exibir_vetor(v, n, "Selection Sort");

    // Teste 3: Insertion Sort
    for (int i = 0; i < n; i++) v[i] = original[i];
    insertion_sort(v, n);
    exibir_vetor(v, n, "Insertion Sort");

    // Teste 4: Quick Sort
    for (int i = 0; i < n; i++) v[i] = original[i];
    quick_sort(v, 0, n - 1);
    exibir_vetor(v, n, "Quick Sort");

    // Teste 5: Busca Binária
    int chave = 45;
    int pos = busca_binaria(v, n, chave);
    printf("\nBusca Binaria pela chave %d: ", chave);
    if (pos != -1) {
        printf("Encontrada com sucesso na posicao de indice %d!\n", pos);
    } else {
        printf("Chave nao encontrada.\n");
    }

    printf("\nConcluido com sucesso!\n");
    return 0;
}