Programa simples em c

Aqui está um exemplo de como você pode implementar o programa com as duas funções de ordenação, o Bubble Sort e o Quick Sort. O programa compara o número de comparações e trocas realizadas por ambas as funções nos três cenários (melhor caso, caso médio e pior caso).

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

#define SIZE 500

// Contadores globais para comparações e trocas
int comparisons_bubble = 0, swaps_bubble = 0;
int comparisons_quick = 0, swaps_quick = 0;

// Função auxiliar para trocar elementos
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Implementação do Bubble Sort
void bubbleSort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n-1; i++) {
        for (j = 0; j < n-i-1; j++) {
            comparisons_bubble++; // Comparação
            if (arr[j] > arr[j+1]) {
                swap(&arr[j], &arr[j+1]);
                swaps_bubble++; // Troca
            }
        }
    }
}

// Função auxiliar para o Quick Sort
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        comparisons_quick++; // Comparação
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
            swaps_quick++; // Troca
        }
    }
    swap(&arr[i + 1], &arr[high]);
    swaps_quick++; // Troca
    return (i + 1);
}

// Implementação do Quick Sort
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Função para preencher o vetor com números aleatórios
void fillRandom(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % 1000;
    }
}

// Função para preencher o vetor em ordem crescente
void fillAscending(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        arr[i] = i;
    }
}

// Função para preencher o vetor em ordem decrescente
void fillDescending(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        arr[i] = n - i;
    }
}

// Função para copiar um vetor para outro
void copyArray(int src[], int dest[], int n) {
    for (int i = 0; i < n; i++) {
        dest[i] = src[i];
    }
}

// Função para resetar os contadores
void resetCounters() {
    comparisons_bubble = swaps_bubble = 0;
    comparisons_quick = swaps_quick = 0;
}

// Função para imprimir os resultados em formato de tabela
void printResults(const char* case_type) {
    printf("%-15s | %-15d | %-15d | %-15d | %-15d\n", case_type, comparisons_bubble, swaps_bubble, comparisons_quick, swaps_quick);
}

int main() {
    int arr[SIZE], temp[SIZE];

    // Semente para números aleatórios
    srand(time(0));

    printf("%-15s | %-15s | %-15s | %-15s | %-15s\n", "Caso", "Comp. Bubble", "Trocas Bubble", "Comp. Quick", "Trocas Quick");
    printf("-----------------------------------------------------------------------------------------------\n");

    // Melhor caso (vetor já em ordem crescente)
    fillAscending(arr, SIZE);
    copyArray(arr, temp, SIZE);
    bubbleSort(arr, SIZE);
    quickSort(temp, 0, SIZE - 1);
    printResults("Melhor caso");

    // Caso médio (vetor aleatório)
    resetCounters();
    fillRandom(arr, SIZE);
    copyArray(arr, temp, SIZE);
    bubbleSort(arr, SIZE);
    quickSort(temp, 0, SIZE - 1);
    printResults("Caso médio");

    // Pior caso (vetor em ordem decrescente)
    resetCounters();
    fillDescending(arr, SIZE);
    copyArray(arr, temp, SIZE);
    bubbleSort(arr, SIZE);
    quickSort(temp, 0, SIZE - 1);
    printResults("Pior caso");

    return 0;
}

Explicação:

1. Funções de Ordenação:

   • bubbleSort: Implementa o algoritmo Bubble Sort e conta o número de comparações e trocas.
   • quickSort: Implementa o Quick Sort com particionamento, também contando comparações e trocas.

2. Casos de Teste:

   • Melhor Caso: O vetor já está ordenado em ordem crescente.
   • Caso Médio: O vetor é preenchido com valores aleatórios.
   • Pior Caso: O vetor está em ordem decrescente.

3. Preenchimento do Vetor:

   • fillRandom: Preenche o vetor com números aleatórios.
   • fillAscending: Preenche o vetor em ordem crescente.
   • fillDescending: Preenche o vetor em ordem decrescente.

4. Comparações e Trocas: O programa compara o número de comparações e trocas feitas por cada algoritmo nos três casos e imprime os resultados em formato de tabela.
   
   Exemplo de Saída:
   
   Caso            | Comp. Bubble    | Trocas Bubble  | Comp. Quick     | Trocas Quick
   ---------------------------------------------------------------------------------------
   Melhor caso     | 124750          | 0              | 747             | 748
   Caso médio      | 124875          | 31193          | 2580            | 1267
   Pior caso       | 124750          | 124750         | 2581            | 1267