Pular para conteúdo

5. Algoritmos clássicos: escrevendo na mão

Sobre este capítulo

Este é o único capítulo do curso que anda na direção contrária à do resto. Em todos os outros, a pergunta é "o que o C++ já me dá pronto?". Aqui, é "o que acontece dentro dessas ferramentas?".

Você vai escrever à mão seis algoritmos que a biblioteca padrão já tem. Não é para usar assim no dia a dia — no capítulo 8 cada um deles vira uma linha. É para que, quando essa linha aparecer, você saiba exatamente o que ela está fazendo, quanto ela custa, e o que dá errado quando dá.

Você acabou de ganhar o std::vector, que carrega o próprio tamanho e cresce sozinho. Com ele e com o que você já sabe de C — for, if, uma variável auxiliar — dá para resolver quase todo problema clássico de coleção. Este capítulo faz exatamente isso.

Busca linear: percorrer até achar

O problema mais simples: onde está o valor?

#include <vector>

int busca_linear(const std::vector<int>& v, int alvo) {
    for (int i = 0; i < static_cast<int>(v.size()); i++) {
        if (v[i] == alvo) {
            return i;
        }
    }
    return -1;
}

Três coisas a notar.

O return dentro do laço encerra a função assim que acha — não adianta continuar procurando. Muita gente escreve uma variável encontrado e percorre o vector inteiro mesmo depois de ter achado; funciona, mas faz trabalho à toa.

O -1 é o "não achei", e ele serve aqui porque nenhum índice válido é negativo — como discutido no capítulo 3. Guarde a ressalva de lá: no dia em que a função devolver um valor em vez de um índice, -1 passa a ser uma resposta legítima, e aí o retorno tem de ser bool com o resultado saindo por referência.

E o static_cast<int> em volta de v.size() é o do capítulo 4: size() devolve std::size_t, sem sinal, e comparar com um int gera aviso. Num laço tão simples quanto este, std::size_t i = 0 também serviria — daqui para a frente, porém, os índices deste capítulo entram em contas que podem ficar negativas, e por isso o tamanho passa sistematicamente por um int.

Quanto custa: no pior caso, uma passada pelo vector inteiro. Com 1.000 elementos, até 1.000 comparações.

Máximo e mínimo: guardar o melhor até agora

int maior_elemento(const std::vector<int>& v) {
    int maior = v[0];              // NAO comece em 0
    for (int x : v) {
        if (x > maior) {
            maior = x;
        }
    }
    return maior;
}

O erro clássico desta função é inicializar maior = 0. Com {-5, -2, -9}, a resposta sairia 0 — um valor que nem está no vector. O único ponto de partida honesto é o primeiro elemento.

Isso tem uma consequência: a função exige um vector não vazio, porque v[0] não existe num vector vazio. Ou você documenta essa exigência, ou muda a assinatura para bool maior_elemento(const std::vector<int>& v, int& maior) e trata o caso — e aqui não dá para usar um -1, porque o que volta é um valor do vector, e -1 é um valor possível. É a decisão do capítulo 3.

Se você precisa do índice do maior, e não do valor, guarde o índice e compare v[i] > v[indice_maior].

Contagem e acumulação: uma variável que sobrevive ao laço

Contar quantos elementos satisfazem uma condição:

int conta_pares(const std::vector<int>& v) {
    int total = 0;
    for (int x : v) {
        if (x % 2 == 0) {
            total++;
        }
    }
    return total;
}

Somar, e daí tirar a média:

double media(const std::vector<double>& v) {
    if (v.empty()) {
        return 0.0;
    }
    double soma = 0.0;
    for (double x : v) {
        soma += x;
    }
    return soma / v.size();
}

São o mesmo padrão: uma variável declarada antes do laço, atualizada dentro dele, lida depois. Se você declarar total dentro do for, ela é recriada a cada volta e o resultado é sempre 0 ou 1 — é o erro que mais aparece nas primeiras semanas.

Na média, repare no if (v.empty()): sem ele, um vector vazio faz uma divisão por zero. E soma é double, não int — somar notas em int descarta as casas decimais antes mesmo da divisão.

Trocar dois elementos

Antes de ordenar, é preciso saber trocar de lugar:

void troca(std::vector<int>& v, int i, int j) {
    int temporario = v[i];
    v[i] = v[j];
    v[j] = temporario;
}

A variável temporária não é opcional. Sem ela, v[i] = v[j]; v[j] = v[i]; deixa os dois com o mesmo valor: o primeiro já foi sobrescrito quando a segunda linha o lê. Desenhe as duas caixas e execute as duas linhas com o dedo — é assim que se enxerga o problema.

Repare que o vector vai por std::vector<int>&, sem const: a função precisa alterá-lo.

Bubble sort: ordenar comparando vizinhos

A ideia é simples de enunciar: percorra o vector comparando cada par de vizinhos e trocando quando estiverem fora de ordem. Uma passada põe o maior valor no fim. Repita até que nenhuma troca seja necessária.

void bubble_sort(std::vector<int>& v) {
    if (v.size() < 2) {
        return;            // vazio ou com um elemento: ja esta ordenado
    }
    bool trocou = true;
    while (trocou) {
        trocou = false;
        for (std::size_t i = 0; i < v.size() - 1; i++) {
            if (v[i] > v[i + 1]) {
                troca(v, i, i + 1);
                trocou = true;
            }
        }
    }
}

Vale executar isto no papel com {3, 1, 2} antes de rodar.

Três detalhes que valem mais que o algoritmo em si:

O laço de fora é um while, e o de dentro é um for. Não é capricho: ninguém sabe de antemão quantas passadas serão necessárias — só se sabe quando parar, que é quando uma passada inteira não troca nada. Já dentro de uma passada, sabemos exatamente até onde ir: do primeiro par ao último. Laço com fim conhecido é for; laço que para por uma condição é while.

A guarda if (v.size() < 2) logo na primeira linha é o que torna v.size() - 1 seguro. É exatamente a armadilha do sem-sinal vista no capítulo 4: num vector vazio, v.size() - 1 não dá -1, dá o maior número possível, e o laço sairia percorrendo memória que não é sua. Com a guarda, a conta só é feita quando o vector tem pelo menos dois elementos — e aí v.size() - 1 é no mínimo 1.

A bandeira trocou é a própria condição do while: começa true para garantir a primeira passada, e cada passada a zera e só a religa se trocar alguém. É ela que transforma "sempre n² comparações" em "uma passada só, quando o vector já está ordenado".

Dá para economizar um pouco mais: depois de cada passada, o maior valor que faltava já está na posição final, e o laço interno poderia parar mais cedo a cada volta. Aqui ficamos com a versão em que toda passada vai até o fim — mais simples de ler, e a diferença não muda a ordem de grandeza do custo.

Quanto custa: no pior caso, aproximadamente n² comparações. Com 1.000 elementos, cerca de um milhão. É por isso que ninguém usa bubble sort de verdade — mas é o algoritmo de ordenação mais fácil de entender, e entender um é o que permite confiar nos outros.

Busca binária: o prêmio por ter ordenado

Ordenar dá trabalho. Este é o retorno desse investimento:

int busca_binaria(const std::vector<int>& v, int alvo) {
    int inicio = 0;
    int fim = static_cast<int>(v.size()) - 1;

    while (inicio <= fim) {
        int meio = (inicio + fim) / 2;
        if (v[meio] == alvo) {
            return meio;
        }
        if (v[meio] < alvo) {
            inicio = meio + 1;      // o alvo so pode estar na metade de cima
        } else {
            fim = meio - 1;          // ...ou na de baixo
        }
    }
    return -1;
}

A cada volta, metade dos candidatos é descartada. Num vector de 1.000 elementos, a busca linear faz até 1.000 comparações; a binária faz no máximo 10. Com um milhão de elementos: um milhão contra 20.

O preço é a exigência: o vector precisa estar ordenado. Numa lista bagunçada, a busca binária devolve resposta errada sem reclamar — não é um erro que o compilador possa pegar.

inicio <= fim, com <=, é o que garante que o último candidato seja examinado; com <, a função erra quando sobra um elemento só.

Mediana: quando ordenar é o próprio problema

A mediana é o valor do meio de um conjunto ordenado. Se a quantidade é par, é a média dos dois centrais.

double mediana(std::vector<int> v) {     // por VALOR: vamos ordenar a copia
    if (v.empty()) {
        return 0.0;
    }
    bubble_sort(v);                       // o mesmo da secao anterior
    int meio = static_cast<int>(v.size()) / 2;
    if (v.size() % 2 == 1) {
        return v[meio];
    }
    return (v[meio - 1] + v[meio]) / 2.0;
}

Repare no parâmetro: std::vector<int> v, por valor. Em todo o resto do curso a recomendação é const std::vector<T>&, para não copiar — mas aqui a função precisa ordenar, e ordenar o vector de quem chamou seria um efeito colateral surpreendente. Copiar é a escolha certa, e é deliberada.

O / 2.0, e não / 2, garante divisão em ponto flutuante: com {1, 2} a mediana é 1.5, não 1.

Erros comuns

"Meu contador sempre dá 1" — a variável foi declarada dentro do laço, e é recriada a cada volta. Ela tem que ser declarada antes.

Máximo dando 0 num vector de negativos — maior foi inicializado em 0 em vez de v[0].

comparison of integer expressions of different signedness — comparar int i com v.size(), que é sem sinal. Use std::size_t i ou static_cast<int>(v.size()). Veja o capítulo 4.

Laço que percorre memória alheia num vector vazio — a expressão v.size() - 1 num vector vazio não dá -1; como size() é sem sinal, dá o maior número possível. Guarde o tamanho num int antes do laço, ou garanta antes que o vector tem elementos, como faz o bubble_sort.

Troca que apaga um dos valores — faltou a variável temporária.

Busca binária devolvendo resposta errada — o vector não estava ordenado. O algoritmo não tem como perceber isso.

Resumo

  • Busca linear percorre até achar; custa uma passada.
  • Máximo e mínimo começam em v[0], nunca em 0.
  • Contagem e acumulação usam uma variável declarada antes do laço.
  • Trocar dois elementos exige uma variável temporária.
  • Bubble sort compara vizinhos e troca; custa cerca de n² comparações, e por isso não se usa na prática.
  • Busca binária descarta metade dos candidatos a cada passo, mas exige vector ordenado.
  • size() é sem sinal: v.size() - 1 num vector vazio é uma armadilha.

Nada disso se escreve à mão num programa de verdade. No capítulo 8, depois da Avaliação 1, cada uma dessas funções vira uma chamada de uma linha — e aí você já vai saber o que essa linha faz por dentro.