Estabilidade e o custo de ordenar

O que é uma ordenação estável

Imagine ordenar uma lista de alunos por nota. Dois alunos tiraram 8, o João e a Maria, e na lista original o João aparecia antes. Uma ordenação estável garante que, depois de ordenar por nota, o João continue antes da Maria entre os que tiraram 8; a ordem original dos empatados é preservada. Uma ordenação instável pode inverter os dois sem motivo. Parece um detalhe, mas vira importante quando você ordena por mais de um critério em sequência. Um exemplo comum: você tem uma lista de pedidos e quer ordená-la por cliente e, dentro de cada cliente, por data. O truque é ordenar primeiro por data e depois por cliente, com um método estável: a ordenação por cliente mantém a ordem por data entre os pedidos do mesmo cliente. Sem estabilidade, a segunda ordenação bagunçaria a primeira.

O custo dos métodos simples

Os três métodos que você aprendeu, bolha, seleção e inserção, compartilham um mesmo defeito: são lentos para listas grandes. A raiz do problema é que todos, de um jeito ou de outro, comparam os itens uns com os outros num padrão que faz o número de operações crescer com o quadrado do tamanho da lista. Dobrar o tamanho não dobra o trabalho, quadruplica. Você já viu essa relação nos laços aninhados e no contraste da busca linear com a binária: é o crescimento que explode. Para dez itens, esses métodos fazem cerca de cem operações, o que é instantâneo. Para um milhão de itens, fariam cerca de um trilhão, o que levaria um tempo absurdo. É por isso que, apesar de intuitivos, eles não servem para ordenar dados grandes de verdade.

A boa notícia é que gente muito inteligente resolveu esse problema décadas atrás. Existem algoritmos de ordenação rápidos, com nomes como ordenação por intercalação e ordenação rápida, que usam a estratégia de dividir para conquistar: quebram a lista em partes menores, ordenam cada parte e as combinam com esperteza. Esses métodos ordenam um milhão de itens numa fração de segundo, com um custo que cresce de forma muito mais suave que o quadrado. Você não precisa implementá-los agora, o raciocínio deles é mais avançado, mas precisa saber que existem e que é neles que as linguagens de programação se baseiam. Quando você chama a função de ordenar pronta de uma linguagem, é um desses algoritmos rápidos e testados que roda por baixo, não a bolha.

Fechando: da ordenação para a eficiência

A ordenação foi um exemplo perfeito de uma verdade que atravessa a computação: existem muitos jeitos de resolver o mesmo problema, e eles podem custar coisas radicalmente diferentes. A bolha e a ordenação rápida entregam a mesma lista ordenada, mas uma leva um tempo absurdo onde a outra leva um instante. Escolher o algoritmo certo não é preciosismo; é a diferença entre um programa que funciona e um que trava. Ao longo dos módulos de busca e ordenação, você viu essa ideia aparecer repetidas vezes: linear contra binária, bolha contra métodos rápidos, laço simples contra aninhado. Está na hora de dar nome a ela e aprender a medir o custo de um algoritmo de forma geral, sem matemática pesada. Esse é o assunto do próximo módulo, a eficiência e a famosa notação Big-O, que amarra tudo o que você viu até aqui.