Ordenação Básica

Três jeitos de arrumar as mesmas oito cartas

Ordenar é rearranjar uma sequência de forma que cada elemento seja menor ou igual ao próximo. Só isso. Para conseguir, basta uma coisa: um critério de comparação entre dois elementos. Pode ser o valor de um número, o tamanho de uma string, a data de um registro ou uma combinação deles. Sem critério não existe ordenação; com critério, qualquer algoritmo deste artigo funciona sobre qualquer tipo de dado.

Os três que vamos ver resolvem o problema com estratégias que não se parecem em nada:

Acompanhe os três sobre o mesmo array. Troque de algoritmo mantendo a entrada, e depois troque a entrada mantendo o algoritmo: são dois experimentos diferentes, e os dois têm resposta.

Um detalhe que parece decoração e não é: a faixa verde tem dois significados. No bubble e no selection ela marca posições definitivas, que o algoritmo nunca mais toca. No insertion ela marca um trecho ordenado entre si, que ainda vai receber elementos no meio. Confundir os dois é o erro mais comum de quem está aprendendo, porque leva a achar que o insertion sort já resolveu posições que ele ainda vai empurrar.

Bubble sort: só troca com o vizinho

A regra é uma linha: percorra o array comparando cada elemento com o seguinte e troque quando estiverem fora de ordem.

def bubble_sort(a):
    n = len(a)
    for fim in range(n - 1, 0, -1):
        trocou = False
        for j in range(fim):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                trocou = True
        if not trocou:
            break        # já estava ordenado

Depois da primeira passada existe uma certeza: o maior valor está na última posição. Ele não tem como ter ficado em outro lugar, porque toda comparação que ele venceu o empurrou uma casa adiante. Por isso a passada seguinte pode parar uma posição antes, e é isso que o fim decrescente faz. Sem esse detalhe o algoritmo continua correto e faz trabalho jogado fora.

A trocou é a otimização que muda o comportamento de verdade. Se uma passada inteira não trocou nada, então cada elemento já é menor ou igual ao seguinte, ou seja, o array está ordenado e não há mais nada a fazer. Com um array já ordenado de 8 posições, isso reduz o trabalho de 28 comparações para 7.

Repare no tipo de movimento: toda troca do bubble sort acontece entre vizinhos. Nenhum elemento pula por cima de outro. Guarde isso, porque é daí que sai a estabilidade dele.

Selection sort: escolhe primeiro, escreve depois

Aqui a lógica se inverte. Em vez de arrumar aos poucos, o algoritmo decide de uma vez quem é o dono de cada posição, da esquerda para a direita.

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        menor = i
        for j in range(i + 1, n):
            if a[j] < a[menor]:
                menor = j
        if menor != i:
            a[i], a[menor] = a[menor], a[i]

Para saber quem é o menor do trecho restante, não tem jeito: é preciso olhar todos. E é aqui que mora a característica mais estranha do selection sort. Ele faz exatamente n(n-1)/2 comparações sempre, para qualquer entrada. Com 8 elementos são 28 comparações no array embaralhado, 28 no array invertido e 28 no array que já chegou pronto. Melhor caso, caso médio e pior caso são o mesmo número.

Em compensação, ele é o algoritmo que menos escreve. Cada rodada termina em no máximo uma troca, então o total nunca passa de n - 1 trocas, ou 2(n-1) escritas. No array invertido de 8 posições, o selection sort faz 8 escritas contra 56 do bubble sort. Isso importa quando escrever é caro: memória flash com número limitado de ciclos, registros grandes que custam a copiar, estruturas que disparam um log a cada alteração.

E existe o preço. A troca do selection sort é longa: ele pega um elemento que pode estar do outro lado do array e o traz direto para a posição atual, passando por cima de tudo que estiver no caminho. Nada no algoritmo confere se algum desses elementos atropelados tinha a mesma chave.

Insertion sort: a mão de cartas

Este é o algoritmo que você já usa sem saber. Quando alguém distribui cartas e você organiza a mão, pega uma carta por vez e a encaixa no lugar certo entre as que já estão arrumadas, deslizando as maiores para abrir espaço. Isso é insertion sort.

def insertion_sort(a):
    for i in range(1, len(a)):
        atual = a[i]      # a carta na mão
        j = i - 1
        while j >= 0 and a[j] > atual:
            a[j + 1] = a[j]   # abre espaço
            j -= 1
        a[j + 1] = atual  # encaixa

Duas decisões merecem atenção. A primeira é o laço começar em 1: o trecho de um elemento só já está ordenado por definição, então não há o que fazer com a posição 0. A segunda é a variável atual. Sem ela o algoritmo se perde: o primeiro deslocamento (a[j + 1] = a[j]) sobrescreve justamente a posição de onde veio o elemento que está sendo colocado. Guardar o valor antes é o que permite empurrar os vizinhos sem perdê-lo.

A condição de parada é a[j] > atual, com maior estrito. Quando o insertion sort encontra alguém igual, ele para e encaixa logo depois. Trocar esse > por >= continua ordenando certo e destrói a estabilidade do algoritmo, o que é um bom lembrete de quanto pode depender de um caractere.

O ponto forte é o melhor caso. Se o array já está quase ordenado, cada elemento anda pouquíssimo para trás e o while quase não roda. No preset "quase ordenado", com uma única inversão, o insertion sort resolve em 8 comparações, contra 13 do bubble sort e as 28 inevitáveis do selection sort. É por isso que ele é o único dos três que sobrevive dentro das bibliotecas modernas.

Inversões: a conta que os três pagam de forma diferente

Existe um número que explica o custo dos três de uma vez, e ele não depende de nenhum deles: a quantidade de inversões da entrada. Uma inversão é um par de posições i < j em que a[i] > a[j], ou seja, um par que está fora de ordem entre si. Um array já ordenado tem 0 inversões; um array invertido de 8 posições tem as 28 possíveis.

A relação é exata, não aproximada:

• Bubble sort troca exatamente uma vez por inversão. Cada troca entre vizinhos desfaz uma inversão, e só uma. Logo, escritas = 2 × inversões.
• Insertion sort desloca exatamente uma vez por inversão, mais uma escrita por elemento colocado. Logo, escritas = inversões + (n - 1).
• Selection sort não paga por inversão nenhuma. Ele desfaz várias inversões de uma vez com um único salto longo, e é por isso que escreve tão pouco.

Isso dá um jeito honesto de ler a diferença entre os três. Bubble e insertion são sensíveis à desordem da entrada; o selection é sensível apenas ao tamanho. Nenhum deles escapa do O(n²), porque o número de inversões pode chegar a n(n-1)/2, e aí a conta fecha no quadrado.

Estável quer dizer que o empate não se mexe

Um algoritmo de ordenação é estável quando dois elementos de chave igual saem na mesma ordem em que entraram. Não é sobre estar certo: as três saídas abaixo estão corretas pelo critério de ordenação. É sobre o que acontece no empate.

Bubble e insertion são estáveis, selection não é, e a causa é mecânica em vez de decorada. Repare no card de distância da maior troca. Bubble e insertion só mexem em vizinhos, então toda troca tem distância 1, e uma troca de distância 1 não tem como pular por cima de ninguém. O selection troca com um elemento que pode estar a n - 1 casas dali, e é esse salto que atropela o empate.

Onde isso importa de verdade é em ordenação encadeada. Ordenar uma lista por nome e depois por prioridade só produz o resultado esperado ("por prioridade e, dentro dela, por nome") se o segundo sort for estável. Com um sort instável, o segundo passo embaralha o que o primeiro tinha arrumado.

Em Python isso é explícito: list.sort() e sorted() são garantidamente estáveis pela documentação da linguagem, e ordenar em duas passadas é uma técnica documentada justamente por causa disso. Em outras linguagens a garantia varia, e vale conferir antes de contar com ela.

O(n²) é o teto, não a sentença

A pergunta natural é por que estudar algoritmos que ninguém usa. A resposta é que um deles é usado, e muito.

Nenhuma biblioteca padrão séria implementa um algoritmo de ordenação só. O sorted do Python usa Timsort, e o std::sort do C++ usa introsort: os dois trocam para insertion sort quando o trecho fica pequeno, tipicamente abaixo de algumas dezenas de elementos. O motivo é o que este artigo mediu. Num trecho pequeno e quase ordenado, o insertion sort faz pouquíssimas comparações, não aloca nada, percorre memória contígua e não paga o custo fixo de chamada recursiva que um O(n log n) cobra. O termo quadrático existe, mas com n pequeno ele perde para as constantes.

Vale também acertar um vocabulário que costuma sair torto. O, Ω e Θ são limites de uma função, não sinônimos de pior, melhor e caso médio:

Melhor caso, caso médio e pior caso são um eixo independente: cada um desses cenários é uma função, e cada função pode ser descrita com qualquer uma das três notações. Dá para dizer que o pior caso do insertion sort é Θ(n²), que é mais forte e mais preciso do que dizer O(n²). O costume de falar só em O vem de a garantia superior ser a que interessa na hora de dimensionar um sistema. Se o assunto ainda estiver nebuloso, vale voltar em Big O.

Por fim, o limite que fecha o assunto: nenhum algoritmo baseado em comparações consegue ordenar em menos de O(n log n) no pior caso. Não é falta de criatividade, é contagem: com n elementos existem n! arranjos possíveis, cada comparação distingue no máximo dois casos, e são necessárias pelo menos log₂(n!) comparações para separar todos, o que dá aproximadamente n log₂ n. Os três algoritmos deste artigo estão longe desse limite; merge sort, quick sort e heap sort o alcançam, cada um por um caminho diferente. E counting sort escapa dele por não comparar nada, o que só é possível sob condições bem específicas.

Vídeo da aula

Direto do canal da comunidade Craft & Code Club · 1:52:10.

▶

Problemas para praticar

Na ordem em que recomendamos resolver. Marque os que você já fez, fica salvo aqui.

Referências

Artigos e materiais externos para se aprofundar.