Tony Hoare não conhecia os algoritmos de ordenação padrão. Então inventou Quicksort.

Em 1959, Tony Hoare estudava tradução automática em Moscou quando encontrou um problema muito prático: o dicionário inglês que o programa precisava usar estava armazenado em uma longa fita magnética.

Ler a fita do começo ao fim levava minutos.

Se o programa procurasse uma palavra, rebobinasse e depois procurasse a próxima, a tradução seria dolorosamente lenta.

Hoare fez então uma pergunta mais simples.

E se as palavras da frase fossem ordenadas na mesma ordem alfabética do dicionário?

Assim a fita precisaria passar apenas uma vez.

Havia um problema.

Hoare não conhecia os algoritmos de ordenação padrão.

Então inventou um.

Esse algoritmo virou Quicksort.

O problema real não era “como ordenar?”

O problema real era a fita.

Uma fita magnética não funciona como memória de acesso aleatório moderna. Para chegar a uma entrada mais adiante, é preciso atravessar fisicamente o que vem antes. Voltar custa caro.

O dicionário já estava armazenado em ordem alfabética.

Se as palavras a traduzir também fossem ordenadas, todas as buscas poderiam acontecer durante uma única passagem para frente.

Hoare precisava de um método de ordenação rápido o bastante para que essa ideia valesse a pena.

Mais tarde ele recordou que não havia estudado os métodos existentes. O algoritmo surgiu de raciocinar diretamente sobre a estrutura do problema.

A ideia central cabe em um guardanapo

Escolha um item como pivot.

Coloque itens menores de um lado.

Itens maiores do outro.

Repita o mesmo processo nos dois grupos menores.

Esse é o coração do Quicksort.

Os detalhes importam. Um pivot ruim pode produzir um worst case muito ruim. Boas implementações exigem partitioning cuidadoso e decisões práticas de engenharia.

Mas o movimento conceitual é pequeno.

Em vez de procurar repetidamente o próximo menor elemento, divida o problema em duas versões menores de si mesmo.

Grande desordem vira desordem menor.

Quicksort transformou uma restrição em estrutura

A fita era lenta de uma maneira específica.

Essa limitação obrigou Hoare a pensar na ordem dos acessos.

O resultado não ficou preso à fita magnética.

Virou um dos algoritmos de ordenação mais conhecidos da ciência da computação.

Esse padrão aparece repetidamente em engenharia.

Limite de memória cria uma estrutura de dados melhor.

Limite de banda cria uma codificação melhor.

Limite de bateria cria um scheduling melhor.

Uma etapa manual dolorosa cria automação.

A restrição parece a coisa que impede o progresso.

Às vezes é justamente o que revela a forma da solução.

Não conhecer a resposta padrão pode ajudar de vez em quando

A versão perigosa desta lição seria dizer que ignorância é boa.

Não é.

Conhecer o trabalho existente normalmente economiza anos de esforço desperdiçado.

A lição mais estreita é outra.

Quando você entende profundamente o problema de base, não estar preso à implementação habitual pode deixar uma estrutura diferente aparecer.

Hoare não estava chutando.

Sabia exatamente qual custo queria eliminar.

Sabia o que a máquina estava fazendo lentamente.

Essa clareza importou mais do que conhecer um catálogo de técnicas de sorting.

Equipes de software ainda otimizam a camada errada

Uma página está lenta, então reescrevem o frontend.

O gargalo real é um round trip ao banco de dados.

O build está lento, então compram runners mais rápidos.

O problema real é invalidation de dependências.

Um workflow de IA está caro, então trocam de modelo.

O problema real é o mesmo contexto sendo processado cinco vezes.

Quicksort não começou com “vamos inventar um algoritmo lendário”.

Começou com “pare de rebobinar a fita”.

Hoare passou o restante da carreira tornando programas mais fáceis de raciocinar

Quicksort foi apenas uma parte do trabalho dele.

Hoare fez contribuições fundamentais a linguagens de programação, correção de programas e concorrência. Hoare logic ofereceu uma forma rigorosa de raciocinar sobre o que um programa deve garantir antes e depois de executar. Communicating Sequential Processes influenciou profundamente a teoria de sistemas concorrentes.

Ele recebeu o ACM Turing Award por contribuições fundamentais ao design e à definição de linguagens de programação.

O fio comum é claro.

Pegue um processo complicado.

Encontre a estrutura por baixo.

Torne essa estrutura explícita o bastante para que humanos consigam raciocinar sobre ela.

A pergunta útil costuma estar uma camada abaixo

“Precisamos de busca mais rápida” pode significar “estamos varrendo os mesmos dados vezes demais”.

“Precisamos de mais gente” pode significar “há trabalho repetido demais”.

“Precisamos de um algoritmo melhor” pode significar “ainda não identificamos qual operação é realmente cara”.

Todo sistema moderno tem sua própria fita magnética.

Algum recurso é lento.

Alguma transição custa caro.

Alguma ação repetida domina o tempo total.

O que o seu sistema está “rebobinando” repetidamente porque ninguém questionou a ordem do trabalho?

Fontes

• Computer History Museum — Oral History of Sir Antony Hoare
• Microsoft Research — Tony Hoare
• Microsoft Research — biografia e descoberta de Quicksort em Moscou
• Microsoft Research — Tony Hoare speaker biography
• Imagem destacada — Tony Hoare na ETH Zurich em 1994, foto de Andreas F. Borchert, CC BY-SA 4.0 via Wikimedia Commons. Adaptada para uma tela 16:9; a obra derivada permanece sob CC BY-SA 4.0.