Algoritmos de ordenação: merge sort e quick sort

1. Introdução à Ordenação por Divisão e Conquista

Os algoritmos de ordenação baseados no paradigma divisão e conquista revolucionaram a computação ao reduzir a complexidade de tempo de O(n²) para O(n log n). A ideia central é simples: dividir o problema em subproblemas menores, resolver cada um recursivamente e combinar as soluções. Tanto o merge sort quanto o quick sort seguem esse princípio, mas com abordagens distintas na fase de combinação.

Enquanto algoritmos como bubble sort, insertion sort e selection sort exigem comparações na ordem de n² para ordenar n elementos, os algoritmos O(n log n) conseguem processar listas enormes em frações do tempo. Para um vetor de 1 milhão de elementos, a diferença entre O(n²) e O(n log n) é de aproximadamente 500 bilhões de operações contra apenas 20 milhões — uma melhoria de 25.000 vezes.

2. Merge Sort: Princípios e Funcionamento

O merge sort adota uma estratégia de divisão exata: o vetor é dividido recursivamente ao meio até restarem subvetores de um único elemento (que já estão ordenados). A fase de combinação (merge) intercala dois subvetores ordenados em um único vetor ordenado, utilizando um vetor auxiliar para armazenar o resultado temporário.

O algoritmo é naturalmente recursivo e sua implementação requer duas funções principais: mergeSort() para dividir e merge() para intercalar.

3. Implementação do Merge Sort em C

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

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int *L = (int*)malloc(n1 * sizeof(int));
    int *R = (int*)malloc(n2 * sizeof(int));

    memcpy(L, &arr[left], n1 * sizeof(int));
    memcpy(R, &arr[mid + 1], n2 * sizeof(int));

    int i = 0, j = 0, k = left;

    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++;
    }

    free(L);
    free(R);
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Vetor original: ");
    printArray(arr, n);

    mergeSort(arr, 0, n - 1);

    printf("Vetor ordenado: ");
    printArray(arr, n);

    return 0;
}

4. Análise do Merge Sort

Complexidade de tempo: O merge sort apresenta O(n log n) em todos os casos (melhor, médio e pior). Isso ocorre porque a árvore de recursão tem profundidade log₂(n) e cada nível realiza n operações de merge.

Complexidade de espaço: O(n) para os vetores auxiliares alocados em cada chamada de merge. Embora existam implementações que minimizam alocações, o padrão exige memória extra proporcional ao tamanho do vetor.

Estabilidade: O merge sort é estável — elementos iguais mantêm sua ordem relativa original. Isso é crucial quando a ordenação considera múltiplos critérios (ex: ordenar por nome e depois por data).

Aplicações práticas: Ideal para ordenar listas encadeadas (não requer acesso aleatório), processamento de dados externos (arquivos grandes) e sistemas que exigem desempenho previsível, como bancos de dados relacionais.

5. Quick Sort: Princípios e Funcionamento

O quick sort utiliza uma estratégia de divisão baseada em pivô. Um elemento é escolhido como pivô e o vetor é particionado em duas regiões: elementos menores ou iguais ao pivô à esquerda, e elementos maiores à direita. O processo se repete recursivamente em cada partição.

A escolha do pivô é crítica para o desempenho. As estratégias comuns incluem:
- Primeiro elemento (simples, mas suscetível a pior caso)
- Último elemento (usado no algoritmo de Lomuto)
- Mediana de três (primeiro, meio e último — reduz chance de pior caso)

6. Implementação do Quick Sort em C

#include <stdio.h>

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

int particionaLomuto(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = particionaLomuto(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Vetor original: ");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("Vetor ordenado: ");
    printArray(arr, n);

    return 0;
}

7. Análise do Quick Sort

Complexidade de tempo: O caso médio é O(n log n), mas o pior caso é O(n²) quando o pivô é sempre o menor ou maior elemento (ex: vetor já ordenado com pivô no último elemento). A probabilidade de pior caso diminui com boas estratégias de escolha do pivô.

Complexidade de espaço: O(log n) para a pilha de recursão (no caso médio). No pior caso, pode chegar a O(n), mas implementações com recursão na partição menor otimizam isso.

In-place: O quick sort ordena no local, utilizando apenas trocas dentro do próprio vetor, sem necessidade de memória extra significativa.

Não estável: Elementos iguais podem ter sua ordem relativa alterada durante o particionamento.

8. Comparação e Escolha entre Merge Sort e Quick Sort

Quando usar merge sort:
- Estabilidade é requisito (ordenar por múltiplos campos)
- Trabalhando com listas encadeadas (merge sort adapta-se naturalmente)
- O pior caso O(n²) do quick sort é inaceitável (sistemas críticos)
- Dados estão em memória externa (discos, fitas)

Quando usar quick sort:
- Memória é limitada (merge sort requer O(n) extra)
- Desempenho médio é prioridade (quick sort é geralmente mais rápido na prática)
- Dados aleatórios ou com boa distribuição
- Implementações embarcadas com restrições de espaço

Benchmark simples em C:

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

// Protótipos das funções (implementações omitidas por brevidade)
void mergeSort(int arr[], int left, int right);
void quickSort(int arr[], int low, int high);

int main() {
    int n = 100000;
    int *arr1 = (int*)malloc(n * sizeof(int));
    int *arr2 = (int*)malloc(n * sizeof(int));

    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        arr1[i] = rand() % 100000;
        arr2[i] = arr1[i];
    }

    clock_t start = clock();
    mergeSort(arr1, 0, n - 1);
    clock_t end = clock();
    printf("Merge Sort: %.3f ms\n", 
           1000.0 * (end - start) / CLOCKS_PER_SEC);

    start = clock();
    quickSort(arr2, 0, n - 1);
    end = clock();
    printf("Quick Sort: %.3f ms\n", 
           1000.0 * (end - start) / CLOCKS_PER_SEC);

    free(arr1);
    free(arr2);
    return 0;
}

Em testes práticos com vetores aleatórios, o quick sort costuma ser 2 a 3 vezes mais rápido que o merge sort devido à melhor localidade de referência e menor overhead de alocação de memória.

Referências