Ordenação é uma das operações mais fundamentais em ciência da computação. Ela organiza dados em uma ordem específica (geralmente crescente ou decrescente), facilitando buscas, análises e processamentos subsequentes. Nesta aula, vamos mergulhar nos algoritmos de ordenação clássicos, entender suas complexidades e aprender a usar a função qsort disponível na biblioteca padrão de C.

Começaremos com os três algoritmos simples, porém importantes: Bubble Sort, Selection Sort e Insertion Sort. Eles são didáticos e servem como base para entender conceitos como comparação, troca e complexidade. Em seguida, analisaremos a eficiência desses algoritmos e compararemos com a função qsort, que implementa o Quicksort, um algoritmo muito mais rápido para grandes volumes de dados.

Bubble, selection, insertion

Os três algoritmos a seguir são considerados simples e intuitivos. Eles são ótimos para aprender, mas não são recomendados para conjuntos de dados grandes devido à sua complexidade O(n²). Vamos examinar cada um deles em detalhes.

Bubble Sort

O Bubble Sort (ordenação por bolhas) funciona comparando elementos adjacentes e trocando-os se estiverem na ordem errada. Esse processo é repetido até que nenhuma troca seja necessária, indicando que o array está ordenado. O nome vem da ideia de que os elementos maiores “borbulham” para o final do array a cada iteração.

Implementação em C:

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // Otimização: se não houver trocas, o array já está ordenado
        int swapped = 0;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

Exemplo de uso: ordenar um array de inteiros. A complexidade no pior caso é O(n²), mas no melhor caso (array já ordenado) é O(n) com a otimização.

Selection Sort

O Selection Sort (ordenação por seleção) divide o array em duas partes: uma parte ordenada (no início) e uma parte não ordenada. A cada passo, ele encontra o menor elemento da parte não ordenada e o coloca no final da parte ordenada. Esse algoritmo faz menos trocas que o Bubble Sort, mas ainda tem complexidade O(n²).

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // Troca o mínimo com o elemento na posição i
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}

Nota: o Selection Sort é mais eficiente em termos de escrita (menos trocas) se a troca for uma operação custosa.

Insertion Sort

O Insertion Sort (ordenação por inserção) é similar a como organizamos cartas de baralho: pegamos um elemento e o inserimos na posição correta entre os já ordenados. Ele percorre o array da esquerda para a direita, mantendo a parte esquerda sempre ordenada.

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // Move os elementos maiores que key para a direita
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

O Insertion Sort é eficiente para arrays pequenos e para dados quase ordenados, com complexidade O(n) no melhor caso.

Visão de complexidade

A análise de complexidade é crucial para escolher o algoritmo adequado. A notação Big O descreve o comportamento assintótico do algoritmo em relação ao tamanho da entrada (n).

Para os três algoritmos apresentados, a complexidade de tempo no pior caso é O(n²). Isso significa que, se o tamanho da entrada dobrar, o tempo de execução quadruplica. Em contraste, algoritmos mais avançados como Quicksort têm complexidade média O(n log n), muito mais eficiente para grandes volumes.

Além do tempo, devemos considerar a complexidade de espaço. Os algoritmos apresentados são in-place, ou seja, usam apenas uma quantidade constante de memória extra (O(1)), o que é uma vantagem.

Tabela comparativa (valores aproximados para n = 1000):

  • Bubble Sort: ~1.000.000 operações
  • Selection Sort: ~500.000 operações
  • Insertion Sort: ~250.000 operações (melhor caso)
  • Quicksort (qsort): ~10.000 operações (log linear)

Essa diferença torna os algoritmos simples inadequados para grandes conjuntos de dados.

qsort da stdlib

A biblioteca padrão de C fornece a função qsort, que implementa o algoritmo Quicksort de forma eficiente e genérica. Ela pode ordenar qualquer tipo de dado, desde que você forneça uma função de comparação.

A assinatura da função é:

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

Parâmetros:

  • base: ponteiro para o array a ser ordenado.
  • nmemb: número de elementos.
  • size: tamanho de cada elemento em bytes.
  • compar: função de comparação que retorna negativo, zero ou positivo.

Exemplo de uso com inteiros:

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

int compare_ints(const void *a, const void *b) {
    int ia = *(const int *)a;
    int ib = *(const int *)b;
    return (ia > ib) - (ia < ib);
}

int main() {
    int arr[] = {5, 2, 8, 1, 9};
    size_t n = sizeof(arr) / sizeof(arr[0]);
    qsort(arr, n, sizeof(int), compare_ints);
    for (size_t i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;
}

Para strings, você pode usar strcmp:

int compare_strings(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}

Essa flexibilidade torna o qsort muito poderoso para ordenar qualquer tipo de estrutura.

Comparando

Ao escolher um algoritmo de ordenação, considere o tamanho dos dados, a eficiência temporal e espacial, e a facilidade de implementação.

Os algoritmos simples (Bubble, Selection, Insertion) são adequados para:

  • Arrays pequenos (até algumas centenas de elementos).
  • Fins educacionais, para entender os fundamentos.
  • Quando a simplicidade do código é mais importante que o desempenho.

O qsort é preferível quando:

  • Os dados são grandes (mais de alguns milhares).
  • Você precisa de uma solução robusta e testada.
  • Deseja ordenar diferentes tipos de dados sem reescrever o algoritmo.

No entanto, o qsort não é estável (não preserva a ordem de elementos iguais) e pode ter pior caso O(n²) em algumas implementações, embora seja raro na prática.

Para aplicações críticas, considere implementar ou usar outros algoritmos como Merge Sort (estável) ou Heap Sort (garantido O(n log n)).

Boas práticas

1. Sempre teste seus algoritmos com arrays de tamanhos variados, incluindo casos extremos (vazio, já ordenado, ordem inversa).

2. Utilize qsort quando precisar de ordenação genérica em código de produção.

3. Entenda a função de comparação: ela deve retornar um inteiro negativo, zero ou positivo, não apenas -1, 0, 1.

4. Para arrays de estruturas, compare um campo específico e, se necessário, desempate com outros campos.

5. Lembre-se de que qsort modifica o array original.

Referências

Exercícios

  1. Implemente uma função que ordene um array de inteiros usando Bubble Sort, mas com uma otimização que interrompa o loop se não houver trocas em uma passada. Teste com um array já ordenado e meça o número de iterações.

    ✓ Resposta: Uma implementação com a otimização já foi mostrada acima. No melhor caso, o número de iterações será apenas 1 (a primeira passada não faz trocas).

  2. Escreva um programa que leia N números do usuário, armazene em um array e ordene usando Selection Sort. Imprima o array antes e depois.

    ✓ Resposta: 
    #include <stdio.h>
void selection_sort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min = i;
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[min]) min = j;
        int temp = arr[i]; arr[i] = arr[min]; arr[min] = temp;
    }
}
int main() {
    int n;
    printf("Quantos números? "); scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) { printf("Número %d: ", i+1); scanf("%d", &arr[i]); }
    printf("Antes: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n");
    selection_sort(arr, n);
    printf("Depois: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n");
    return 0;
}

  3. Utilizando qsort, ordene um array de strings (ponteiros para char) em ordem alfabética. Lembre-se de usar strcmp.

    ✓ Resposta: 
    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmpstr(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}
int main() {
    const char *frutas[] = {"banana", "abacaxi", "laranja", "uva"};
    int n = sizeof(frutas)/sizeof(frutas[0]);
    qsort(frutas, n, sizeof(char*), cmpstr);
    for (int i = 0; i < n; i++) printf("%s\n", frutas[i]);
    return 0;
}

  4. Compare o desempenho do Bubble Sort e do qsort para um array de 10.000 inteiros aleatórios. Meça o tempo de execução com clock() e exiba os tempos.

    ✓ Resposta: 
    #include <stdio.h>
#include <stdlib.h>
#include <time.h>
void bubble_sort(int arr[], int n) { /* implementação completa */ }
int cmp(const void *a, const void *b) { return (*(int*)a - *(int*)b); }
int main() {
    int n = 10000;
    int arr[n], arr2[n];
    srand(time(NULL));
    for (int i = 0; i < n; i++) arr[i] = arr2[i] = rand()%100000;
    clock_t t1 = clock(); bubble_sort(arr, n); t1 = clock() - t1;
    clock_t t2 = clock(); qsort(arr2, n, sizeof(int), cmp); t2 = clock() - t2;
    printf("Bubble: %f s\n", ((double)t1)/CLOCKS_PER_SEC);
    printf("qsort: %f s\n", ((double)t2)/CLOCKS_PER_SEC);
    return 0;
}

  5. Explique por que o Insertion Sort é eficiente para arrays quase ordenados e dê um exemplo prático onde isso seria útil.

    ✓ Resposta: O Insertion Sort tem complexidade O(n) no melhor caso (quando o array já está ordenado ou quase), porque ele faz poucas comparações e deslocamentos. Um exemplo prático é a ordenação de dados que são continuamente atualizados, como uma lista de pontuações em um jogo online, onde novos elementos são inseridos em uma lista já ordenada.