Saltar para o conteúdo
Topos Uranos
Português

Buscar e ordenar

Resumo

Buscar e ordenar são os dois problemas fundamentais sobre coleções, e entre eles há uma troca: ordenar uma vez custa, mas barateia cada busca posterior. A aula escreve à mão a busca linear e a binária, que, sobre dados ordenados, descarta a metade a cada passo; justifica a binária com o seu invariante, prova que termina, conta as suas iterações e estuda os três erros que a arruínam. Seguem-se as ordenações por seleção e por inserção, com os seus invariantes e a contagem exata das suas comparações; depois, os mesmos problemas com a biblioteca de ranges, e a conta que decide quando convém ordenar antes de buscar.

Objetivos de aprendizagem

  1. Implementar a busca linear e a binária, e justificar a binária com o seu invariante (“se o valor está, está entre low e high”), com a prova de que termina.
  2. Implementar a ordenação por seleção e por inserção, enunciar o invariante de cada uma e contar as suas comparações no melhor e no pior caso.
  3. Usar std::ranges::sort, std::ranges::contains, std::ranges::find, std::ranges::binary_search e std::ranges::lower_bound no lugar das versões próprias quando for o caso, respeitando as suas pré-condições.
  4. Decidir, segundo o número de buscas previstas, se convém ordenar os dados antes de buscar neles, e justificar a decisão com a contagem de comparações.

Busca linear

Buscar é responder, dada uma coleção e um valor, se o valor está e onde. Sem informação sobre a ordem dos dados, não há outra estratégia senão olhá-los um por um: é a busca linear. Quando o valor não está, este curso devolve values.size(), a primeira posição que não pertence ao vetor: não é um índice válido, de modo que não se confunde com uma resposta, e é a mesma convenção que a biblioteca segue, como se verá na quinta seção.

Programa em C++
#include <cstddef>#include <print>#include <vector>​// Pré-condição: nenhuma.// Pós-condição: devolve o menor índice i com values[i] == target,// ou values.size() se target não está.std::size_t linearSearch(const std::vector<int>& values, int target){    // Invariante: target não está em values[0], ..., values[i - 1].    for (std::size_t i{0}; i < values.size(); ++i) {        if (values[i] == target) {            return i;        }    }    return values.size();}​int main(){    const std::vector<int> codes{405, 112, 318, 207, 112, 530};    for (const int target : {207, 112, 999}) {        const std::size_t pos{linearSearch(codes, target)};        if (pos == codes.size()) {            std::println("{}: não está", target);        } else {            std::println("{}: posição {}", target, pos);        }    }}
Saída
207: posição 3112: posição 1999: não está

O invariante da linha 10 dá a correção. No começo, com i igual a 0, afirma algo sobre um trecho vazio e é verdadeiro. Se vale no começo de uma iteração e values[i] não é o buscado, vale no fim dela com um elemento a mais. Ora, o laço tem duas saídas: se return i; é executado, values[i] é o buscado e, pelo invariante, nenhum elemento anterior o era, donde i é a primeira ocorrência (por isso o 112, que aparece duas vezes, é informado na posição 1); se o laço termina pela condição, i vale values.size() e o invariante diz que o valor não está em parte alguma. O return dentro do laço termina a função, e com ela o laço, e poupa uma flag.

O custo, no sentido da aula O custo de um algoritmo, mede-se pelas comparações values[i] == target. Se o valor não está, fazem-se exatamente nn, uma por elemento: o pior caso. Se está na posição pp, fazem-se p+1p + 1. A busca linear é, então, O(n)O(n): com o dobro de dados, o dobro de trabalho. Sem informação adicional não se pode fazer melhor: um algoritmo que deixasse de olhar um elemento não saberia se o valor estava ali.