Bubble Sort (Ordenação por Flutuação)

• Visão geral: Geralmente o primeiro algoritmo de ordenação aprendido por iniciantes, considerado fundamental.
• Eficiência: Muito baixa. O tempo de ordenação torna-se extremamente longo quando o volume de dados atinge um certo patamar.
• Princípio: Cada elemento é comparado com os demais; se a condição for satisfeita, os elementos trocam de posição, caso contrário, nenhuma ação é tomada.
• Complexidade de tempo: O(n²)
• Complexidade de espaço: O(1)
• Estabilidade: Estável

void bubble_sort(int dados[], int tamanho) {
    int temporario;
    for (int atual = 0; atual < tamanho - 1; ++atual) {
        for (int compara = 0; compara < tamanho - atual - 1; ++compara) {
            if (dados[compara] > dados[compara + 1]) {
                temporario = dados[compara];
                dados[compara] = dados[compara + 1];
                dados[compara + 1] = temporario;
            }
        }
    }
}

Insertion Sort (Ordenação por Inserção)

• Visão geral: Um método de ordenação simples e direto.
• Eficiência: Baixa, comparável ao Bubbble Sort em termos de desempenho.
• Princípio: Começando do segundo elemento, guarda seu valor e o compara iterativamente com os anteriores. Se a condição for atendida, insere o elemento na posição correta; caso contrário, continua a comparação. Se nenhuma posição adequada for encontrada, insere o elemento no início.
• Complexidade de tempo: O(n²)
• Complexidade de espaço: O(1)
• Estabilidade: Estável

void insertion_sort(int vetor[], int n) {
    int chave, pos;
    for (int i = 1; i < n; ++i) {
        chave = vetor[i];
        pos = i - 1;
        while (pos >= 0 && vetor[pos] > chave) {
            vetor[pos + 1] = vetor[pos];
            pos--;
        }
        vetor[pos + 1] = chave;
    }
}

Shell Sort

• Visão geral: Um algoritmo avançado, uma otimização do Insertion Sort. O array é dividido em subconjuntos com base em um incremento, e cada subconjunto é ordenado individualmente usando o Insertion Sort.
• Eficiência: Relativamente alta.

void shell_sort(int arranjo[], int tamanho) {
    int intervalo;
    for (intervalo = tamanho / 2; intervalo > 0; intervalo /= 2) {
        for (int i = intervalo; i < tamanho; i++) {
            int valor_temp = arranjo[i];
            int j;
            for (j = i; j >= intervalo && arranjo[j - intervalo] > valor_temp; j -= intervalo) {
                arranjo[j] = arranjo[j - intervalo];
            }
            arranjo[j] = valor_temp;
        }
    }
}

Quick Sort (Ordenação Rápida)

• Visão geral: Um dos algoritmos de ordenação mais rápidos na prática, mas não é estável. Implementado recursivamente.
• Eficiência: Muito alta.
• Princípio: Seleciona um elemento pivô. Particiona o array de modo que elementos menores que o pivô fiquem à esquerda e os maiores à direita. O processo é repetido recursivamente nas sublistas resultantes.
• Complexidade de tempo: O(n log n)
• Complexidade de espaço: O(log n)
• Estabilidade: Instável

void particiona(int arr[], int baixo, int alto) {
    int pivo = arr[alto];
    int i = (baixo - 1);
    for (int j = baixo; j <= alto - 1; j++) {
        if (arr[j] < pivo) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[alto];
    arr[alto] = temp;
    return (i + 1);
}

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

Merge Sort (Ordenação por Intercalação)

• Visão geral: O algoritmo de ordenação estável mais eficiente. Implementado recursivamente.
• Eficiência: Muito alta.
• Princípio: Divide o array recursivamente pela metade até que cada subarray tenha um único elemento. Depois, intercala (combina) os subarrays de forma ordenada, construindo o array ordenado final.
• Complexidade de tempo: O(n log n)
• Complexidade de espaço: O(n)
• Estabilidade: Estável

void intercala(int arr[], int esq, int meio, int dir) {
    int i, j, k;
    int n1 = meio - esq + 1;
    int n2 = dir - meio;
    int L[n1], R[n2];
    for (i = 0; i < n1; i++)
        L[i] = arr[esq + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[meio + 1 + j];
    i = 0;
    j = 0;
    k = esq;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void merge_sort(int arr[], int esq, int dir) {
    if (esq < dir) {
        int meio = esq + (dir - esq) / 2;
        merge_sort(arr, esq, meio);
        merge_sort(arr, meio + 1, dir);
        intercala(arr, esq, meio, dir);
    }
}