Ordenação 1: bubble sort, selection sort e insertion sort

O selection sort faz exatamente 45 comparações em qualquer lista de 10 valores, esteja ela embaralhada ou já em ordem.

Pondo as coisas em ordem

Ordenar quer dizer rearranjar uma lista para que os valores vão do menor para o maior (ou por nome, data, preço, qualquer ordem que se possa comparar). É um dos trabalhos mais comuns de um computador: os contatos do celular, os resultados de busca por relevância, uma coluna de planilha ordenada por data. Ordenar também facilita outros trabalhos. Como a unidade anterior mostrou, uma lista ordenada pode ser buscada com busca binária, e numa lista ordenada os valores repetidos ficam lado a lado.

Esta unidade trata de três métodos simples. Os três funcionam comparando dois valores por vez e movendo valores dentro da própria lista. São curtos de escrever e fáceis de acompanhar, e os três ficam muito lentos em listas compridas. Ver por que eles ficam lentos é a melhor preparação para os métodos mais rápidos da próxima unidade. O tempo todo, contamos duas coisas: comparações (perguntar "este valor é maior que aquele?") e trocas (trocar dois valores de lugar).

Bubble sort: troque vizinhos fora de ordem

O bubble sort (ordenação por bolha) percorre a lista comparando cada par de vizinhos. Quando o da esquerda é maior, ele troca os dois. Depois de uma passada completa, o maior valor foi levado passo a passo até a ponta direita, como uma bolha subindo, e nunca mais precisa se mover. A passada seguinte pode parar uma casa antes. Uma melhoria comum é observar se houve uma passada sem nenhuma troca: isso quer dizer que tudo já está em ordem, então a ordenação pode parar antes.

Acompanhe na lista [5, 1, 4, 2, 8]. A primeira passada compara 5 e 1 (troca), 5 e 4 (troca), 5 e 2 (troca), 5 e 8 (deixa): a lista agora é [1, 4, 2, 5, 8] e o 8 está no lugar. A segunda passada compara 1 e 4, 4 e 2 (troca), 4 e 5, e dá [1, 2, 4, 5, 8]. A terceira passada compara 1 e 2, depois 2 e 4, não faz troca e para. Total: 4 + 3 + 2 = 9 comparações e 4 trocas.

function bubbleSort(a) {
  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;
    for (let j = 0; j < a.length - 1 - pass; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];  // troca
        swapped = true;
      }
    }
    if (!swapped) break;  // já está ordenada
  }
  return a;
}

Selection sort: ache o menor e ponha em seguida

O selection sort (ordenação por seleção) funciona do jeito como muita gente arruma as cartas na mão. Percorra a lista inteira atrás do menor valor e troque-o para a primeira posição. Depois percorra o resto atrás do menor valor que sobrou e troque-o para a segunda posição, e assim por diante. Em [5, 1, 4, 2, 8], a primeira varredura acha o 1 e o troca com o 5; a segunda acha o 2 e o troca com o 5; as duas últimas varreduras acham 4 e 5 já no lugar. São só 2 trocas, mas as varreduras ainda comparam 4 + 3 + 2 + 1 = 10 vezes.

O selection sort nunca para antes. Mesmo numa lista que já está ordenada, ele ainda precisa verificar cada valor restante para ter certeza de que achou o menor. Para n valores, as comparações sempre somam (n − 1) + (n − 2) + … + 1 = n(n − 1)/2. Para 10 valores isso dá 45; para 100 valores, 4950; para 1000 valores, 499 500. O ponto forte dele é o número pequeno de trocas: no máximo n − 1, o que importa quando mover um valor custa caro.

Insertion sort: deslize cada valor novo até o lugar

O insertion sort (ordenação por inserção) mantém a parte esquerda da lista ordenada e a aumenta um valor por vez. Ele pega o próximo valor e o move para a esquerda, trocando com o vizinho, até o vizinho não ser maior. Aí esse valor está no lugar entre os ordenados. Numa lista que já está quase em ordem, cada valor novo anda só um ou dois passos, então o insertion sort é muito rápido nesse caso. Em [5, 1, 4, 2, 8] ele faz 7 comparações e 4 trocas.

Contando as trocas: inversões

Há um jeito elegante de prever quantas trocas o bubble sort e o insertion sort precisam. Conte as inversões: pares de valores que estão na ordem errada um em relação ao outro. Em [5, 1, 4, 2, 8] as inversões são (5, 1), (5, 4), (5, 2) e (4, 2), quatro ao todo. Cada troca de dois vizinhos fora de ordem corrige exatamente uma inversão e não cria nenhuma, então os dois métodos fazem exatamente 4 trocas. Uma lista invertida de n valores tem todos os pares invertidos, n(n − 1)/2 inversões, que é o pior caso.

Cada célula mostra comparações / trocas. A lista de exemplo é [5, 1, 4, 2, 8]. O bubble sort aqui é a versão que para depois de uma passada sem troca.

Os três métodos têm a mesma fraqueza. No pior caso, cada um compara mais ou menos todos os pares de valores, cerca de n²/2 comparações. Dobre a lista e o trabalho fica quatro vezes maior. Dez vezes a lista quer dizer cem vezes o trabalho. Para algumas dezenas de valores isso pouco importa; para um milhão é inviável, e a próxima unidade mostra como fazer muito melhor.