Entendendo os algoritmos de ordenação clássicos com Big O

Quantas vezes você já precisou ordenar uma lista de elementos em sua aplicação e simplesmente chamou o método nativo .sort() da linguagem de sua preferência? Seja em JavaScript, Python ou Java, é extremamente comum confiarmos cegamente nessas abstrações no nosso dia a dia de desenvolvimento.

No entanto, você já se perguntou qual algoritmo está rodando por trás dessa instrução e até onde ele continua sendo eficiente? Em um cenário real com milhões de registros, confiar em um método sem conhecer sua complexidade computacional pode ser a diferença entre um sistema performático e um colapso total de processamento.

Exploraremos a teoria, a notação Big O e os pseudocódigos dos principais algoritmos de ordenação: Selection Sort, Quick Sort e Bubble Sort.

1. A Armadilha da Abstração e a Notação Big O

Quando trabalhamos com conjuntos pequenos de dados, como 30 ou 100 itens, quase qualquer algoritmo apresentará um tempo de resposta imperceptível. Porém, a engenharia de software exige que pensemos em grande escala.

Para medir o impacto do volume de dados no tempo de execução, utilizamos a Notação Big O. O termo O(n) indica que o tempo de execução cresce proporcionalmente ao número de elementos n da lista.

Regra importante: Ignorando as Constantes

Na análise assintótica do Big O, as constantes matemáticas são desconsideradas. Por exemplo, um algoritmo que faz O(1/2 * n²) operações é simplificado diretamente para O(n²). Isso acontece porque, quando n chega à casa dos milhões ou bilhões, cortar o tempo pela metade continua deixando o número na mesma ordem de grandeza astronômica.

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

O Selection Sort é um dos algoritmos mais intuitivos e simples. A lógica consiste em percorrer a lista inteira, encontrar o menor (ou maior) elemento, posicioná-lo no início (ou em uma nova lista) e repetir o processo para os elementos restantes.

Complexidade de Tempo

• Pior caso: O(n²)
• Caso médio: O(n²)
• Melhor caso: O(n²)

Como o algoritmo precisa realizar comparações aninhadas para cada item da lista, seu comportamento é quadrático em todos os cenários.

Pseudocódigo: Selection Sort

Veja a estrutura básica que você pode traduzir para a sua linguagem favorita:

funcao selectionSort(lista)
    n = tamanho(lista)
    
    para i de 0 ate n - 1 faca
        indiceMenor = i
        
        para j de i + 1 ate n - 1 faca
            se lista[j] < lista[indiceMenor] entao
                indiceMenor = j
            fimSe
        fimPara
        
        se indiceMenor != i entao
            trocar(lista[i], lista[indiceMenor])
        fimSe
    fimPara
    
    retornar lista
fimFuncao

3. Quick Sort: A Estratégia Dividir para Conquistar

O Quick Sort é um dos algoritmos de ordenação mais eficientes e utilizados na prática (inclusive compondo bibliotecas padrão de linguagens como C e Java). Ele opera através da estratégia de Dividir para Conquistar utilizando a recursão.

Como Funciona o Quick Sort

• Caso Base: Listas com 0 ou 1 elemento já estão ordenadas por natureza. A recursão para aqui.
• Escolha do Pivô: Seleciona-se um elemento da lista para ser a referência (pivô).
• Particionamento: A lista é dividida em duas sublistas: uma com elementos menores que o pivô e outra com elementos maiores.
• Recursão e Junção: O Quick Sort é chamado recursivamente para as sublistas, e o resultado final é combinado: [menores] + [pivô] + [maiores].

Complexidade de Tempo

• Caso médio: O(n log n). O fator log n vem da divisão sucessiva do problema ao meio, enquanto o n deriva do loop de particionamento.
• Pior caso: O(n²). Ocorre quando a escolha do pivô é ruim (por exemplo, escolher sempre o maior ou menor elemento em uma lista que já está ordenada).

Pseudocódigo: Quick Sort

Abaixo está a implementação conceitual recursiva do Quick Sort:

funcao quickSort(lista)
    se tamanho(lista) < 2 entao
        retornar lista // Caso Base
    fimSe

    pivo = lista[0] // Escolhendo o primeiro elemento como pivô
    menores = listaVazia()
    maiores = listaVazia()

    para cada elemento em lista[1..fim] faca
        se elemento <= pivo entao
            adicionar(menores, elemento)
        senao
            adicionar(maiores, elemento)
        fimSe
    fimPara

    retornar concatenar(quickSort(menores), pivo, quickSort(maiores))
fimFuncao

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

O Bubble Sort é frequentemente ensinado em cursos introdutórios. Ele percorre a lista repetidamente, comparando pares de elementos adjacentes e trocando-os de lugar se estiverem na ordem errada. Os maiores elementos "flutuam" para o final da lista como bolhas.

Complexidade de Tempo

• Pior caso: O(n²)
• Caso médio: O(n²)
• Melhor caso: O(n) (quando a lista já está ordenada e há uma flag de controle de trocas).

Pseudocódigo: Bubble Sort

funcao bubbleSort(lista)
    n = tamanho(lista)
    
    para i de 0 ate n - 1 faca
        trocou = falso
        
        para j de 0 ate n - i - 2 faca
            se lista[j] > lista[j + 1] entao
                trocar(lista[j], lista[j + 1])
                trocou = verdadeiro
            fimSe
        fimPara
        
        // Se nenhuma troca ocorreu nesta passagem, a lista ja esta ordenada
        se nao trocou entao
            interromper
        fimSe
    fimPara
    
    retornar lista
fimFuncao

5. Tabela Comparativa de Desempenho

Para visualizar a diferença gritante de escala entre as complexidades de tempo, considere o impacto hipotético na execução ao ordenar um conjunto com 1.000 elementos:

Algoritmo	Complexidade (Caso Médio)	Complexidade (Pior Caso)	Desempenho Estimado (1.000 itens)
Selection Sort	O(n²)	O(n²)	Lento (~27 horas em escala comparativa)
Bubble Sort	O(n²)	O(n²)	Muito Lento (Loops Aninhados)
Quick Sort	O(n log n)	O(n²)	Muito Rápido (~996 segundos na mesma escala)

Considerações finais

Conhecer o que está por trás do método .sort() transforma a forma como escrevemos código. Embora na maioria dos casos as funções nativas sejam extremamente otimizadas, compreender o comportamento do Quick Sort, do Selection Sort e a mecânica das partições e da notação Big O fornece a autonomia necessária para diagnosticar gargalos e tomar decisões arquiteturais corretas ao trabalhar com grandes volumes de dados.

Agora que você possui o pseudocódigo em mãos, escolha a sua linguagem de programação principal (seja JavaScript, Python, C#, Java ou Go) e implemente cada um desses algoritmos para fixar o aprendizado na prática!

Feito!