Algoritmos de Busca e Ordenação

1. Buscar um item numa coleção

"Esse item está aqui? E se estiver, onde?" é, sem exagero, uma das perguntas mais feitas em qualquer programa — buscar um usuário por ID, um produto por nome, uma palavra num texto. Existem duas estratégias fundamentais para responder essa pergunta, e a diferença entre elas é um dos exemplos mais didáticos de como a notação Big O se traduz em impacto real.

2. Busca linear — O(n)

A busca linear é a estratégia mais direta possível: comece do primeiro item e vá comparando um por um até encontrar o valor procurado (ou até acabar a coleção, se o valor não existir). Ela funciona em qualquer coleção, ordenada ou não.

O custo: no pior caso (o item procurado está na última posição, ou não existe), é necessário olhar todos os n itens. Isso é O(n).

3. Busca binária — O(log n)

A busca binária é muito mais rápida, mas exige uma condição: a coleção precisa estar ordenada. A ideia é a mesma do dicionário físico mencionada no capítulo anterior — abra no meio, compare, e descarte a metade que não pode conter o valor procurado. Repita esse processo na metade restante, até sobrar um único item ou até a resposta ser encontrada.

Cada comparação elimina metade dos candidatos restantes. Numa coleção de 1 milhão de itens, a busca binária encontra qualquer valor (ou confirma que ele não existe) em no máximo cerca de 20 comparações — contra até 1 milhão de comparações da busca linear no pior caso.

FUNÇÃO buscaLinear(vetor, alvo)
    PARA i DE 0 ATÉ tamanho(vetor) - 1
        SE vetor[i] = alvo ENTÃO
            RETORNE i
        FIM SE
    FIM PARA
    RETORNE -1  // não encontrado
FIM FUNÇÃO

FUNÇÃO buscaBinária(vetorOrdenado, alvo)
    início ← 0
    fim ← tamanho(vetorOrdenado) - 1

    ENQUANTO início ≤ fim
        meio ← (início + fim) DIV 2

        SE vetorOrdenado[meio] = alvo ENTÃO
            RETORNE meio
        SENÃO SE vetorOrdenado[meio] < alvo ENTÃO
            início ← meio + 1   // descarta metade da esquerda
        SENÃO
            fim ← meio - 1      // descarta metade da direita
        FIM SE
    FIM ENQUANTO

    RETORNE -1  // não encontrado
FIM FUNÇÃO

4. Ordenar uma coleção

Colocar dados em ordem — crescente ou decrescente — é outro problema fundamental, e é o que torna a busca binária possível. Existem dezenas de algoritmos de ordenação, com diferentes trade-offs. Aqui vamos entender um deles a fundo, passo a passo, porque entender um bem ensina o raciocínio geral por trás de todos os outros: o bubble sort (ordenação por bolha).

5. Bubble sort passo a passo

A ideia do bubble sort é simples: percorrer a coleção comparando pares de itens vizinhos, e trocar os dois de posição sempre que estiverem fora de ordem. Isso é repetido em várias passadas até que nenhuma troca seja mais necessária — nesse ponto, a coleção está ordenada.

O nome vem do comportamento visual do algoritmo: a cada passada, o maior valor ainda fora do lugar vai "borbulhando" até sua posição final, como uma bolha subindo num líquido.

FUNÇÃO bubbleSort(vetor)
    n ← tamanho(vetor)
    PARA i DE 0 ATÉ n - 2
        PARA j DE 0 ATÉ n - 2 - i
            SE vetor[j] > vetor[j + 1] ENTÃO
                // troca os dois de posição
                temp ← vetor[j]
                vetor[j] ← vetor[j + 1]
                vetor[j + 1] ← temp
            FIM SE
        FIM PARA
    FIM PARA
    RETORNE vetor
FIM FUNÇÃO

Um trace com o vetor [5, 2, 8, 1] ajuda a visualizar:

A cada passada completa, o maior valor restante "borbulha" até sua posição correta no final — por isso a segunda passada não precisa mais comparar a última posição, e a terceira não precisa comparar as duas últimas. É esse encolhimento progressivo que o n - 2 - i no pseudocódigo representa.

6. A complexidade do bubble sort

Repare que o bubble sort é, essencialmente, um laço dentro de outro laço, ambos percorrendo (aproximadamente) o tamanho da coleção. Isso é O(n²) — a mesma classe de complexidade discutida no capítulo 1. Para coleções pequenas, isso não é um problema perceptível. Para coleções grandes, é caro.

7. Algoritmos mais eficientes (e por que você raramente os escreve do zero)

Existem algoritmos de ordenação bem mais eficientes que o bubble sort, com complexidade O(n log n) — significativamente melhor que O(n²) para coleções grandes, como mostra a tabela do capítulo 1. Os dois mais conhecidos são:

• Quicksort: escolhe um "pivô" e particiona a coleção em valores menores e maiores que ele, ordenando cada partição recursivamente.
• Merge sort: divide a coleção repetidamente ao meio até sobrarem pedaços de um item, e então vai mesclando os pedaços de volta já ordenados.

Você não precisa memorizar a implementação desses algoritmos agora. Na prática profissional, praticamente nenhuma linguagem moderna espera que você reimplemente ordenação do zero — todas trazem uma função de ordenação pronta na biblioteca padrão (como Array.prototype.sort() em JavaScript), já otimizada e testada em produção. O que importa é entender o que está acontecendo por baixo quando você chama essa função, e saber que a complexidade dela normalmente é O(n log n) — informação que orienta decisões maiores, como se vale a pena ordenar uma coleção antes de buscar nela várias vezes.

8. Juntando busca e ordenação

A razão pela qual esses dois assuntos formam um capítulo só: ordenar tem um custo (O(n log n) com um bom algoritmo), mas esse investimento se paga quando a coleção vai ser buscada repetidamente depois — cada busca binária subsequente custa só O(log n) em vez de O(n). Se a coleção é buscada uma única vez, ordenar antes normalmente não compensa. Se ela é buscada centenas de vezes, ordenar uma vez e usar busca binária depois é quase sempre a escolha certa.