18. Ordenação linear e limites por comparação

Este capítulo nasce das 40 questões publicadas sobre Ordenação linear e limites por comparação. A leitura do acervo revelou 4 núcleos de conhecimento, aqui reorganizados como uma explicação progressiva: primeiro o vocabulário e o modelo mental, depois os mecanismos, as decisões de implementação, os limites e a forma de verificar o comportamento do sistema.

A apostila começa pelos fundamentos usados para representar problemas e construir soluções corretas e eficientes. Estruturas, operações, invariantes e custos serão tratados como partes do mesmo raciocínio. Este é o capítulo 18 de 20 da disciplina Algoritmos e Estruturas de Dados. Ele retoma Merge Sort, Quick Sort e Heap Sort e utiliza essa base para avançar. Na sequência, estudaremos Recursão, backtracking e paradigmas de projeto.

O fio condutor

O desenvolvimento de software começa com um problema e avança por decisões que precisam permanecer compreensíveis e verificáveis. Requisitos orientam modelos; modelos orientam código e arquitetura; testes verificam comportamento; e a operação devolve informações para o próximo ciclo. Uma falha importante no início tende a se espalhar pelas etapas seguintes.

Neste capítulo, use Ordenação linear e limites por comparação para acompanhar quatro perguntas: qual problema precisa ser resolvido, como o mecanismo funciona, que consequências a escolha produz e como o resultado será verificado. Essa sequência transforma termos técnicos em decisões que podem ser explicadas e testadas.

Parte 1 — Fundamentos e vocabulário

Começamos por Parte 1 — Fundamentos e vocabulário, pois essa base organiza os conceitos e exemplos que aparecerão no restante do capítulo.

Limite Ω(n log n)

O ponto de partida é estabelecer o significado do conceito e o problema que ele procura organizar. Limite Ω(n log n) vale para ordenação geral baseada apenas em comparações no modelo decisório. O enunciado delimita corretamente a natureza e a finalidade de limite Ω(n log n). Conceitualmente, limite Ω(n log n) vale para ordenação geral baseada apenas em comparações no modelo decisório. Na prática, isso requer delimitar o significado e o escopo de limite Ω(n log n) e, a partir disso, usar propriedades das chaves quando permitem superar o limite de comparação. O erro recorrente é confundir limite Ω(n log n) com um conceito vizinho ou aplicar Counting Sort a intervalo enorme sem custo de memória; sua prevenção não é mera formalidade, porque altera segurança, previsibilidade ou resultado. A conclusão deve ser auditada por este critério: restrições de domínio justificam tempo linear; a definição operacional de limite Ω(n log n) permite classificar casos de fronteira. A regra ganha sentido quando suas consequências orientam a implementação.

Na prática, isso significa delimitar o significado e o escopo de limite Ω(n log n) e, a partir disso, usar propriedades das chaves quando permitem superar o limite de comparação. Transforme a regra em uma decisão observável: identifique entrada, estado, sequência, saída, falhas possíveis e ambiente. Assim fica claro quando a técnica se aplica e o que precisa ser testado.

Use como teste da compreensão: Restrições de domínio justificam tempo linear; a definição operacional de limite Ω(n log n) permite classificar casos de fronteira. Depois verifique a afirmação com execução controlada, teste automatizado, análise do contrato, medição ou documentação da versão correspondente. A evidência deve reproduzir a propriedade afirmada, inclusive nos casos de erro e de fronteira.