Por que ordenar vale tanto a pena

A ordem destrava tudo

No módulo de busca você viu o superpoder dos dados ordenados: a busca binária acha um item entre um milhão em cerca de vinte passos, mas só funciona se a lista estiver em ordem. Essa é a razão número um para ordenar, e sozinha já justificaria o esforço. Mas a ordem entrega muito mais. Numa lista ordenada, o menor valor é o primeiro e o maior é o último, então achar extremos vira olhar as pontas, sem percorrer nada. Itens iguais ficam vizinhos, o que facilita contar repetições, agrupar por categoria e detectar duplicados. E há o benefício mais óbvio, que a gente nem nota de tão natural: dados ordenados são agradáveis de ler. Todo ranking, catálogo, extrato e lista de resultados que você consulta está ordenado por algum critério, para o seu olho encontrar o que procura.

Vale reparar que a mesma coleção pode ser ordenada de várias formas, conforme o critério, que os programadores chamam de chave de ordenação. Uma lista de contatos pode ser ordenada por nome, para você achar alguém no alfabeto; por data do último contato, para ver quem você não fala há tempos; ou por cidade, para agrupar quem mora perto. A ordenação não muda os dados, muda a disposição deles para servir a um objetivo. Escolher a chave certa é parte de usar bem a ordem: ordenar clientes por valor gasto responde uma pergunta; por data de cadastro, outra. A ordenação é uma ferramenta, e a chave é como você a aponta.

Ordenar é um investimento que se paga

Se a ordem é tão boa, por que não manter tudo sempre ordenado? Porque ordenar custa trabalho, como você viu de relance no módulo anterior, e esse custo precisa valer a pena. A conta é a mesma de afiar o machado: gasta-se um esforço inicial que volta multiplicado nas muitas vezes seguintes. Se você vai buscar uma vez só numa lista bagunçada, a busca linear resolve e ordenar seria desperdício. Mas se a mesma lista será consultada milhares de vezes, ordená-la uma vez e depois usar busca binária em todas as consultas economiza um mundo de esforço. Muitos sistemas mantêm seus dados sempre ordenados justamente porque as consultas são frequentes; outros ordenam sob demanda, quando precisam. Saber quando o investimento compensa é uma decisão de projeto, e depende de quantas vezes a ordem será aproveitada.

Ordenar, a tarefa mais estudada

Poucos problemas foram tão estudados na computação quanto a ordenação. Existem dezenas de algoritmos para ordenar, uns simples e lentos, outros engenhosos e rápidos, e livros inteiros dedicados só a compará-los. Por que tanta atenção a algo que parece trivial? Porque ordenar é onipresente e caro: quase todo sistema precisa ordenar dados, e fazer isso de forma eficiente com milhões de itens exige inteligência. Neste módulo você vai aprender três métodos clássicos e intuitivos, a ordenação da bolha, a por seleção e a por inserção. Eles não são os mais rápidos, e nas linguagens reais você usará ordenações prontas e otimizadas. Mas entender como esses três funcionam, passo a passo, ensina o raciocínio de ordenar e prepara você para entender por que uns métodos são melhores que outros, tema que o módulo de eficiência aprofunda.