Seleção e inserção: dois outros jeitos de ordenar

Seleção: achar o menor e pôr na frente

A ordenação por seleção segue um raciocínio que você usaria para arrumar uma estante do menor ao maior livro sem pressa. Você olha todos os livros, escolhe o menor de todos e o coloca na primeira posição. Depois olha os que sobraram, escolhe o menor deles e o coloca na segunda posição. E repete, sempre selecionando o menor do que ainda falta e o colocando na próxima posição livre. A cada passo, a parte ordenada no começo cresce em um item, e a bagunça no fim encolhe. Quando sobra um item só, ele já está no lugar, e acabou. O nome vem justamente desse gesto de selecionar o menor a cada rodada. É metódico e previsível, e faz poucas trocas, embora precise olhar todos os restantes para achar o menor de cada vez.

Inserção: arrumar as cartas na mão

A ordenação por inserção é tão natural que você provavelmente já a executou hoje sem chamá-la assim. É o que a gente faz ao arrumar as cartas de um jogo na mão. Você pega uma carta de cada vez do monte e a encaixa no lugar certo entre as que já estão organizadas na sua mão, deslizando as maiores para a direita para abrir espaço. As cartas na mão estão sempre ordenadas; cada carta nova encontra seu lugar entre elas. O algoritmo faz igual com a lista: começa considerando o primeiro item como uma mão ordenada de um elemento, e vai pegando os itens seguintes, um a um, inserindo cada um na posição correta entre os já ordenados à esquerda, empurrando os maiores para abrir espaço. Quando o último item é encaixado, a lista inteira está ordenada.

A inserção tem uma qualidade especial que a distingue: ela é rapidíssima quando a lista já está quase ordenada. Se cada item novo já está perto do seu lugar, quase não há empurrões a fazer, e o trabalho é mínimo. Isso a torna útil em situações reais em que os dados chegam quase em ordem, como uma lista já organizada que recebe alguns poucos itens novos. A bolha e a seleção não têm esse atalho: elas fazem o mesmo trabalho pesado independentemente de a lista estar bagunçada ou quase pronta. Essa sensibilidade ao estado inicial dos dados é um primeiro gostinho de como algoritmos diferentes, que resolvem o mesmo problema, podem ter desempenhos bem distintos conforme a situação, ideia central do módulo de eficiência.

Três jeitos, um objetivo

Vale um instante para apreciar o que esses três métodos ensinam. A bolha, a seleção e a inserção resolvem exatamente o mesmo problema, colocar uma lista em ordem, mas por caminhos de raciocínio diferentes: trocar vizinhos, selecionar o menor, encaixar no lugar. Nenhum é mágico, e todos são intuitivos, o que os torna perfeitos para aprender. Eles também compartilham uma limitação: todos ficam lentos com listas grandes, porque no fundo comparam os itens uns com os outros de formas que exigem muito trabalho quando o número cresce. A saída dessa lentidão veio de ideias mais engenhosas, muitas baseadas na recursão e no dividir para conquistar que você aprendeu, que quebram a lista em partes e as ordenam separadamente. Você não precisa dominá-las agora; o importante é ter na cabeça que existe todo um universo de eficiência por trás de algo tão comum quanto ordenar, e é para lá que o curso segue.