Ordenar e eliminar duplicados de uma lista sem surpresas

Ordenar e eliminar duplicados parecem as duas coisas mais simples que se podem fazer a uma lista, e é por isso que os resultados estão tantas vezes discretamente errados. As duas assentam numa comparação, e não há resposta única para o que torna duas linhas iguais ou faz uma linha vir primeiro.

A ordem lexicográfica não é a ordem numérica

A comparação por omissão para texto percorre duas cadeias caráter a caráter, compara pontos de código e para na primeira diferença. Não há nada nela que saiba o que é um número.

input:   img1.png, img2.png, img10.png
sorted:  img1.png, img10.png, img2.png

img10.png fica em segundo lugar porque no quarto caráter 1 (U+0031) é menor do que 2 (U+0032), e a comparação acaba aí. A mesma regra põe a versão 1.10 antes da 1.9 e lista uma pasta de capturas de ecrã fora da ordem em que foram tiradas.

A comparação numérica também resolve os negativos: em ordem lexicográfica, -10 fica entre -1 e -2, porque um sinal de menos é apenas mais um caráter com um ponto de código.

Maiúsculas antes de minúsculas, e outras surpresas dos pontos de código

Em ASCII, as maiúsculas ocupam de 65 a 90 e as minúsculas de 97 a 122, por isso qualquer maiúscula é ordenada antes de qualquer minúscula.

Os dígitos ficam abaixo de todas as letras, o espaço (32) abaixo de todos os carateres imprimíveis, e uma linha vazia abaixo disso, por isso uma ordenação ascendente junta lá em cima as linhas em branco e as que começam por espaço, e uma ordenação descendente junta-as no fundo.

O espaço no fim da linha é a versão invisível do mesmo problema: apple e apple ficam ordenados lado a lado e parecem um duplicado que se recusa a ser removido. O espaço inquebrável (U+00A0) é pior, desenhado exatamente como um espaço normal mas ordenado acima de todas as letras, e o mesmo se passa com o retorno de carro que fica para trás quando um ficheiro Windows é dividido apenas por novas linhas. Se duas linhas parecem idênticas e mesmo assim não se juntam, procure carateres escondidos.

A mesma lista ordena-se de maneira diferente em dois países

A ordem por ponto de código também coloca qualquer caráter acentuado depois de qualquer caráter sem acento. Zürich fica depois de Zzz, e Ärger depois de zebra. Nenhuma língua ordena assim o seu próprio alfabeto. A colação sensível à localidade compara segundo regras de língua, e essas regras não concordam umas com as outras.

Em JavaScript isto vive em Intl.Collator:

const words = ["Zebra", "Ärger", "Apfel"];

words.sort(new Intl.Collator("de").compare);
// Apfel, Ärger, Zebra

words.sort(new Intl.Collator("sv").compare);
// Apfel, Zebra, Ärger

O mesmo objeto cobre os problemas anteriores. { numeric: true } compara sequências de dígitos como números, o que é a ordem natural, e sensitivity define o que conta como diferença: "base" ignora a caixa e os acentos, "accent" ignora só a caixa, "case" ignora só os acentos. Omitir a localidade usa aquilo que estiver configurado na máquina, que é como o mesmo código devolve duas ordens diferentes em dois portáteis. Indique a localidade quando a saída tiver de ser igual em todo o lado.

Que duplicados contam como duplicados

A eliminação de duplicados é tão bem definida quanto o teste de igualdade que lhe está por trás. Veja cinco linhas que aparecem todas como a palavra cafe com acento agudo:

Quatro regras razoáveis dão quatro respostas diferentes:

Nenhuma delas está errada; respondem a perguntas diferentes. A normalização conta mais do que parece, porque o texto vindo de nomes de ficheiro do macOS tende a chegar decomposto (NFD) e o texto vindo do Windows e de formulários web composto (NFC), pelo que uma lista colada a partir de duas origens ganha gémeos invisíveis. O NFKC vai mais longe, reduzindo carateres de compatibilidade como a ligadura fi aos seus equivalentes simples.

Por convenção ganha a primeira ocorrência, por isso, se foi a cópia desalinhada que se colou primeiro, é ela que sobrevive. E remover duplicados é um pedido diferente de encontrar itens únicos: o Remove Duplicate Lines deixa um de cada, ao passo que o conjunto de únicos do List Frequency é o grupo mais pequeno dos itens que aparecem exatamente uma vez.

Estabilidade, e ordenar por duas chaves

Uma ordenação estável garante que as entradas que o comparador considera iguais mantêm a ordem que tinham na entrada. É isso que faz funcionar a ordenação por várias chaves em passagens sucessivas: ordene primeiro pela chave menos importante e depois pela mais importante. Ordenar por nome e depois por departamento dá os departamentos por ordem, com os nomes ordenados dentro de cada um. Uma ordenação instável desfaz a primeira passagem enquanto faz a segunda, e o resultado parece quase certo, o que é pior do que parecer errado.

Inverter tem o mesmo senão, porque virar uma lista ordenada também inverte cada grupo empatado. Use o Reverse List quando o que quer é virar a ordem inteira, não como atalho para uma ordenação descendente.

As implementações diferem. O Array.prototype.sort de JavaScript só é obrigatoriamente estável desde o ES2019; antes disso o V8 usava um quicksort instável acima de um certo tamanho de array, por isso o mesmo código comportava-se de forma diferente com dez itens e com dez mil. O sorted de Python é estável, e o sort do GNU não é, a não ser que lhe passem -s.

Baralhar não é uma forma de ordenar

O baralhamento de uma só linha, list.sort(() => Math.random() - 0.5), é enviesado. Uma ordenação assume que o seu comparador descreve uma ordem consistente e só pergunta pelo subconjunto de pares de que o algoritmo precisa. Um comparador que tira um número novo em cada chamada quebra esse pressuposto, por isso o resultado depende do algoritmo e do comprimento do array: os itens tendem a ficar perto de onde começaram, e algumas permutações aparecem muito mais vezes do que outras.

Um baralhamento correto usa Fisher-Yates, percorrendo do fim para o princípio e trocando cada item por um item escolhido uniformemente na sua posição ou antes dela:

for (let i = list.length - 1; i > 0; i--) {
  const j = Math.floor(Math.random() * (i + 1));
  [list[i], list[j]] = [list[j], list[i]];
}

A variante avariada mais comum usa Math.random() * list.length dentro do ciclo, sorteando de todo o array em cada volta. Isso dá n elevado a n sequências de sorteios igualmente prováveis, número que não se divide de forma exata pelas n fatorial ordenações, por isso algumas ordenações saem mais vezes.

É possível combinar corretamente aleatoriedade e ordenação dando a cada item uma chave aleatória à partida e ordenando por essa chave, porque assim o comparador mantém-se consistente. A falha está em lançar o dado dentro da comparação.

A ordem pela qual os passos vão

A maioria dos problemas com listas vem de fazer as operações certas pela sequência errada.

1. Desembrulhe primeiro. Uma lista copiada de código chega como "apple",; as aspas e a vírgula fazem parte da cadeia, por isso nunca corresponde a apple. O Unwrap List Items remove-as.
2. Faça trim e normalize, para que a igualdade signifique aquilo que julga que significa.
3. Elimine duplicados, com a regra de correspondência escolhida deliberadamente e não aceite como valor por omissão.
4. Ordene. O Sort Lines cobre ordem de texto, numérica, por comprimento e aleatória; acrescente uma localidade para dados acentuados.
5. Mude a forma no fim. O Group List Items corta o resultado em lotes de tamanho fixo para um limite por pedido, e o Rotate List desloca tudo sem alterar a ordem interna.

Eliminar duplicados antes de fazer trim deixa quase-duplicados para trás, e ordenar antes de eliminar duplicados é apenas ordenar linhas que estão prestes a ser deitadas fora.