Algoritmos de ordenação: bubble, insertion, selection

1. Introdução aos Algoritmos de Ordenação Simples

1.1. O que são algoritmos de ordenação e sua importância

Algoritmos de ordenação são procedimentos sistemáticos para rearranjar elementos de uma sequência em uma ordem específica (crescente, decrescente, etc.). São fundamentais na ciência da computação porque dados ordenados permitem buscas mais eficientes (como busca binária), facilitam a detecção de duplicatas e melhoram a performance de muitos outros algoritmos.

1.2. Características comuns: complexidade O(n²) e ordenação in-place

Os três algoritmos abordados neste artigo — bubble sort, insertion sort e selection sort — compartilham duas características principais:
- Complexidade O(n²) no pior caso: o tempo de execução cresce quadraticamente com o tamanho da entrada
- Ordenação in-place: utilizam apenas uma quantidade constante de memória adicional (O(1)), modificando o próprio array original

1.3. Breve comparação com algoritmos mais eficientes

Algoritmos como merge sort (O(n log n)) e quick sort (O(n log n) em média) são significativamente mais rápidos para grandes conjuntos de dados. No entanto, os algoritmos simples são didaticamente valiosos, fáceis de implementar e, em cenários específicos (pequenos arrays ou dados quase ordenados), podem ser competitivos.

2. Bubble Sort (Ordenação por Bolha)

2.1. Funcionamento passo a passo

O bubble sort percorre repetidamente o array, comparando elementos adjacentes e trocando-os se estiverem na ordem errada. A cada iteração completa, o maior elemento "flutua" para sua posição final (como uma bolha), reduzindo o escopo da próxima passagem.

2.2. Implementação em C com otimização

#include <stdio.h>

void bubble_sort(int arr[], int n) {
    int i, j, temp;
    int trocou;

    for (i = 0; i < n - 1; i++) {
        trocou = 0;  // flag de otimização

        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                trocou = 1;
            }
        }

        // Se não houve troca, o array já está ordenado
        if (!trocou) break;
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubble_sort(arr, n);

    printf("Array ordenado: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

2.3. Análise de complexidade

  • Melhor caso (array já ordenado): O(n) — com a flag de otimização, apenas uma passagem é necessária
  • Pior caso (array inversamente ordenado): O(n²) — todas as comparações e trocas são realizadas
  • Caso médio: O(n²)

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

3.1. Princípio

O insertion sort constrói a sequência final ordenada um elemento por vez. Ele pega cada elemento e o insere na posição correta dentro de uma sublista já ordenada, deslocando os elementos maiores para a direita.

3.2. Implementação em C

#include <stdio.h>

void insertion_sort(int arr[], int n) {
    int i, j, chave;

    for (i = 1; i < n; i++) {
        chave = arr[i];
        j = i - 1;

        // Desloca elementos maiores que a chave para a direita
        while (j >= 0 && arr[j] > chave) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = chave;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertion_sort(arr, n);

    printf("Array ordenado: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

3.3. Comportamento e complexidade

  • Melhor caso (array ordenado): O(n) — apenas uma comparação por elemento
  • Pior caso (array inversamente ordenado): O(n²) — máximo de deslocamentos
  • Dados parcialmente ordenados: performance próxima de O(n), tornando-o ideal para pequenos arrays ou dados quase ordenados

4. Selection Sort (Ordenação por Seleção)

4.1. Mecanismo

O selection sort divide o array em duas partes: uma sublista ordenada (à esquerda) e uma sublista não ordenada (à direita). A cada iteração, encontra o menor elemento na parte não ordenada e o troca com o primeiro elemento dessa parte.

4.2. Implementação em C

#include <stdio.h>

void selection_sort(int arr[], int n) {
    int i, j, min_idx, temp;

    for (i = 0; i < n - 1; i++) {
        min_idx = i;

        // Encontra o menor elemento no subarray não ordenado
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }

        // Troca o menor elemento com o primeiro elemento não ordenado
        if (min_idx != i) {
            temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    selection_sort(arr, n);

    printf("Array ordenado: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

4.3. Complexidade invariável

  • Complexidade: O(n²) em todos os casos (melhor, pior e médio)
  • Número de trocas: O(n) — no máximo n-1 trocas, o que é vantajoso quando escrever na memória é caro
  • Número de comparações: sempre n(n-1)/2, independente da ordenação inicial

5. Comparação Prática entre os Três Algoritmos

5.1. Número de comparações vs. trocas

Algoritmo Comparações (pior caso) Trocas (pior caso)
Bubble Sort O(n²) O(n²)
Insertion Sort O(n²) O(n²) (deslocamentos)
Selection Sort O(n²) O(n)

5.2. Estabilidade

  • Bubble Sort: Estável — elementos iguais mantêm a ordem relativa (troca apenas se >, não >=)
  • Insertion Sort: Estável — insere elementos iguais após os existentes
  • Selection Sort: Instável — a troca pode deslocar elementos iguais (exemplo: [5a, 5b, 3] → [3, 5b, 5a])

5.3. Desempenho em diferentes cenários

  • Dados aleatórios: Insertion Sort geralmente é o melhor entre os três para arrays pequenos (< 50 elementos)
  • Dados já ordenados: Insertion Sort e Bubble Sort otimizado são O(n); Selection Sort continua O(n²)
  • Dados inversamente ordenados: Selection Sort pode ser vantajoso devido ao baixo número de trocas

6. Implementação Genérica com Ponteiros e Funções de Comparação

6.1. Uso de void* e ponteiros para função

Para ordenar qualquer tipo de dado em C, podemos usar ponteiros genéricos (void*) e uma função de comparação fornecida pelo usuário.

6.2. Exemplo de adaptação do bubble sort

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

void bubble_sort_generic(void *base, size_t n, size_t size,
                          int (*cmp)(const void*, const void*)) {
    size_t i, j;
    char *arr = (char*)base;
    char temp[size];
    int trocou;

    for (i = 0; i < n - 1; i++) {
        trocou = 0;

        for (j = 0; j < n - i - 1; j++) {
            if (cmp(arr + j * size, arr + (j + 1) * size) > 0) {
                memcpy(temp, arr + j * size, size);
                memcpy(arr + j * size, arr + (j + 1) * size, size);
                memcpy(arr + (j + 1) * size, temp, size);
                trocou = 1;
            }
        }

        if (!trocou) break;
    }
}

// Função de comparação para inteiros
int cmp_int(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubble_sort_generic(arr, n, sizeof(int), cmp_int);

    printf("Array ordenado: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

6.3. Vantagens e limitações

  • Vantagens: Reutilização do código para qualquer tipo de dado (int, float, struct)
  • Limitações: Uso de memcpy para trocas, que é menos eficiente que trocas diretas para tipos primitivos; perda de type safety

7. Considerações Finais e Boas Práticas

7.1. Quando usar cada algoritmo

  • Bubble Sort: Apenas para fins didáticos ou arrays muito pequenos (< 20 elementos)
  • Insertion Sort: Ideal para arrays pequenos (< 50 elementos) ou dados quase ordenados (como parte de algoritmos híbridos)
  • Selection Sort: Útil quando o custo de troca é muito alto (ex: memória flash) ou quando o número de trocas precisa ser minimizado

7.2. Cuidados com desempenho em arrays grandes

Para arrays com mais de 100 elementos, algoritmos O(n²) tornam-se lentos. Prefira algoritmos como merge sort, quick sort ou heap sort para aplicações reais com grandes volumes de dados.

7.3. Leitura complementar

Para aprofundar, estude:
- Merge Sort: ordenação estável O(n log n) baseada em divisão e conquista
- Quick Sort: algoritmo rápido O(n log n) amplamente utilizado em bibliotecas padrão
- Heap Sort: ordenação in-place O(n log n) usando estrutura de heap

Referências