Ordenar texto não é uma só operação: quatro ordens que se dizem todas alfabéticas

Quatro coisas chamadas alfabético

Um botão de ordenar oferece uma opção e dá a entender que existe uma resposta. Existem pelo menos quatro, e não são refinamentos umas das outras: são ordens diferentes que devolvem listas diferentes a partir da mesma entrada. A ordem de unidades de código compara os valores numéricos das unidades UTF-16 que formam a cadeia. A ordem natural lê as séries de dígitos como números. A colação por locale aplica as regras próprias de uma língua sobre que letras contam como a mesma letra. As variantes de colação dividem depois uma mesma língua em várias ordens defensáveis, porque os dicionários alemães e as listas telefónicas alemãs nunca estiveram de acordo.

Tudo o que se segue foi executado, não recordado. Cada lista está impressa exatamente como o Node 26.3 a devolveu, e os scripts são curtos o suficiente para reescrever: um array, um sort, um console.log.

Ordem de unidades de código: o que o .sort() faz mesmo

Chamado sem comparador, o Array.prototype.sort converte cada elemento em cadeia e compara essas cadeias por unidade de código UTF-16. É uma regra documentada, não um acidente, e produz dois sintomas visíveis. As maiúsculas ocupam o intervalo 0x41–0x5A e as minúsculas 0x61–0x7A, por isso toda a maiúscula vem antes de toda a minúscula. E os dígitos são comparados como caracteres: ["capítulo10","capítulo9","capítulo2"] devolve capítulo10, capítulo2, capítulo9, porque «1» é 0x31 e «9» é 0x39, e a comparação para na primeira diferença.

O terceiro sintoma é o que chega ao leitor. Toda a letra com sinal diacrítico vive acima de 0x7A, por isso a ordem de unidades de código empurra o alfabeto acentuado inteiro para trás do z. ["ação","acordo","água","avô"] devolve acordo, avô, ação, água. ["Öl","Ohr","Zebra","Ähre"] devolve Ohr, Zebra, Ähre, Öl. ["ñu","nube","niño","zorro"] devolve niño, nube, zorro, ñu. ["étage","effet","zèbre","Île"] devolve effet, zèbre, Île, étage. Quatro línguas, quatro respostas erradas, uma linha de código.

A ordem de unidades de código não é inútil. É total, transparente, rápida — 20 000 palavras ordenadas em 6 ms no banco de ensaio abaixo — e idêntica em todos os motores e todas as locales, o que a torna a escolha certa para tudo o que uma máquina lê: chaves de índice, baldes de desduplicação, identificadores de cache, serializações canónicas. Só está errada quando a saída é para uma pessoa.

Ordem natural: ler os dígitos como números

A ordem natural — a de um gestor de ficheiros — trata uma série de dígitos dentro de uma cadeia como um único número em vez de uma sequência de caracteres. Em JavaScript é uma opção: new Intl.Collator("pt", { numeric: true }). Sobre ["capítulo10","capítulo9","capítulo2"] devolve capítulo2, capítulo9, capítulo10, e sobre uma lista mais longa ["item2","item9","item10","item100","item20"] devolve item2, item9, item10, item20, item100, onde o .sort() por omissão devolve item10, item100, item2, item20, item9.

Vale a pena conhecer dois limites antes de a ligar em todo o lado. A colação numérica é uma comodidade de apresentação, não aritmética: compara séries de dígitos, por isso tem opiniões sobre «v1.10» face a «v1.9» que um analisador de versões semânticas não partilharia, e nada diz de útil sobre sinais, separadores decimais ou separadores de milhares. E muda a resposta para chaves que apenas por acaso contêm dígitos, como códigos de produto em que 0090 e 90 são artigos diferentes. Ligue-a para listas que uma pessoa percorre, deixe-a desligada para identificadores.

Colação por locale: o alemão contra o sueco

A colação por locale é o caso clássico, e o alemão contra o sueco é o par clássico. Tome ["Öl","Ohr","Zebra","Ähre"]. Sob new Intl.Collator("de") sai Ähre, Ohr, Öl, Zebra: ä é uma variante de a, ö uma variante de o, e o diacrítico só desempata. Sob new Intl.Collator("sv") essas mesmas quatro cadeias saem Ohr, Zebra, Ähre, Öl: em sueco, å, ä e ö são as três últimas letras do alfabeto, depois do z. Nenhum dos dois é um erro. São duas línguas com dois alfabetos, e a lista tem de escolher um.

Agora a parte incómoda: para esta lista, o .sort() por omissão devolve Ohr, Zebra, Ähre, Öl — caráter a caráter a resposta sueca. Um programa que saltou o locale não produziu «nenhuma ordem em particular». Produziu uma ordem estrangeira concreta, em silêncio, e vai continuar a produzi-la para cada lista alemã, espanhola, portuguesa ou francesa em que toque.

As outras locales deste artigo comportam-se do mesmo modo. O espanhol faz do ñ uma letra própria depois do n: ["ñu","nube","niño","zorro"] dá niño, nube, ñu, zorro sob es, ao passo que a ordem de unidades de código exila ñu para trás de zorro. O português trata os acentos como desempates: ["ação","acordo","água","avô"] sai em ordem de dicionário sob pt e baralhado sob .sort(). O italiano dá ancora, Àncora, elite, zucchero sob it, onde o acento é uma diferença secundária e a maiúscula uma terciária. E o francês tem uma ordem verdadeiramente regional: sobre ["cote","coté","côte","côté"], fr devolve cote, coté, côte, côté, enquanto fr-CA devolve cote, côte, coté, côté, porque o francês do Canadá compara os acentos a partir do fim da palavra.

Uma língua, várias ordens: as variantes de colação

Mesmo dentro de uma língua há mais de uma resposta correta, e o CLDR do Unicode entrega-as como variantes com nome, escolhidas através da cadeia de locale. O alemão tem duas de uso diário. A colação de dicionário, de, ordena ["Göbel","Goethe","Godel","Gözde","Gott"] como Göbel, Godel, Goethe, Gott, Gözde: ö é uma variante de o. A colação de lista telefónica, de-u-co-phonebk, ordena as mesmas cinco como Godel, Göbel, Goethe, Gözde, Gott, porque ö é expandido para oe — o que põe Göbel entre Godel e Goethe, exatamente onde procuraria quem busca «Goebel».

Dois botões acompanham a variante e mudam a resposta tanto como ela. sensitivity decide que diferenças contam: sobre «cote» face a «côte» e «cote» face a «Cote», a sensibilidade «base» declara ambos os pares iguais, «accent» separa o acento mas não a caixa, «case» separa a caixa mas não o acento, e «variant» — o valor por omissão — separa ambos. caseFirst decide quem ganha um empate: sobre ["apple","Apple","APPLE"], o valor por omissão devolve apple, Apple, APPLE, e caseFirst: "upper" devolve APPLE, Apple, apple. Nenhum dos dois é cosmético. sensitivity é também o que faz de um colador uma ferramenta de pesquisa: com «base», compare devolve 0 para cadeias que um leitor chamaria a mesma palavra.

Estabilidade: o que acontece aos empates

Uma ordenação é estável quando os elementos que comparam iguais conservam a ordem relativa que tinham na entrada. Isto importa assim que se ordena por uma chave parcial — uma inicial, uma categoria, uma data sem hora — porque os empates não são casos-limite raros: são a maior parte da lista. Ao ordenar dez nomes só pela inicial, os elementos com inicial a saíram nas posições de entrada 1, 2, 4, 6, 8 e os de inicial b nas posições 0, 3, 5, 7, 9: cada grupo conservado, em ordem.

A especificação exige que o Array.prototype.sort seja estável desde ES2019. Antes disso, os motores podiam usar um algoritmo instável acima de certo tamanho de array, e vários usavam: é por isso que os conselhos antigos recomendam um comparador composto ou carregar o índice. A exigência vale seja qual for o tamanho: um array de mil elementos ordenado por uma chave com apenas três valores distintos voltou com cada grupo em ordem de entrada. Pode portanto construir uma ordenação multichave ordenando várias vezes, da chave menos significativa para a mais significativa — primeiro o nome próprio, depois o apelido — e contar com a sobrevivência das passagens anteriores.

O que custa, e a regra que daí decorre

Ordenar com consciência do locale custa mais do que ordenar por unidades de código, mas não o que as pessoas temem, e o erro caro é outro. A ordenar 20 000 palavras no Node 26.3: o .sort() por omissão levou 6 ms, a.localeCompare(b, "de") 12 ms, um colador construído uma vez e reutilizado 28 ms — e construir um new Intl.Collator dentro do comparador levou 1 771 ms, sessenta vezes mais lento do que reutilizá-lo. O custo não é a colação. O custo é construir o colador centenas de milhares de vezes.

Fica uma regra curta o suficiente para se aplicar. Se uma máquina lê a saída, ordene por unidade de código e deixe isso escrito. Se a lê uma pessoa, nomeie um locale — a língua em que o documento está escrito, não a do navegador que o mostra —, construa um só Intl.Collator, decida numeric e sensitivity de propósito, e reutilize-o. A única coisa nunca defensável é chamar .sort() sobre texto visível para o leitor e chamar alfabético ao resultado.

Perguntas frequentes

Porque é que «Zebra» fica antes de «apple»?

Porque o .sort() sem comparador compara unidades de código UTF-16, e toda a maiúscula ASCII (0x41–0x5A) tem um valor menor do que toda a minúscula ASCII (0x61–0x7A). Não ordena letras, ordena números que representam letras. Qualquer colador de locale corrige isso: new Intl.Collator("en").compare dá apple, Banana, zebra, Zebra por essa ordem, com a caixa como último desempate e não como primeiro critério.

A ordenação do JavaScript é estável?

Sim, e é obrigatório. O ES2019 tornou a estabilidade um requisito da especificação para o Array.prototype.sort, e o Array.prototype.toSorted segue a mesma regra. Verificado aqui num array de mil elementos ordenado por uma chave com três valores distintos: cada grupo voltou em ordem de entrada. É essa garantia que permite implementar uma ordenação multicoluna como uma sequência de ordenações de uma coluna, começando pela menos significativa.

Que locale uso se não conheço o do leitor?

Use a língua do conteúdo, não a do dispositivo do leitor. Uma lista de nomes de produtos alemães pertence à colação alemã seja quem for que a olhe, tal como um catálogo alemão impresso. Recorrer ao valor por omissão do motor é a pior opção, porque é invisível: new Intl.Collator() sem argumento resolveu-se para en-US na máquina em que este artigo foi escrito, e resolver-se-ia de outro modo na seguinte, de modo que a mesma lista ficaria ordenada de forma diferente em dois servidores sem mudar uma linha de código.

Porque é que o meu gestor de ficheiros põe item2 antes de item10 e o meu código não?

O gestor de ficheiros usa ordem natural: reconhece a série de dígitos como um número. O seu código compara caracteres, por isso para em «1» face a «9» e nunca lê o resto. Acrescente { numeric: true } a um Intl.Collator, ou passe a mesma opção ao localeCompare, e os dois concordam. Não tente imitar isso enchendo de zeros as cadeias mostradas: isso corrige a ordenação e estraga as etiquetas.

O localeCompare é demasiado lento para uma lista longa?

Por si só não. Sobre 20 000 palavras no Node 26.3, a.localeCompare(b, "de") levou 12 ms e um Intl.Collator reutilizado 28 ms, contra 6 ms do .sort() por omissão — uma diferença que ninguém notará. O que é realmente lento é construir um colador dentro do comparador: assim, a mesma ordenação levou 1 771 ms, porque se fabrica um colador novo para cada uma das centenas de milhares de comparações. Construa-o uma vez, fora da ordenação, e passe o seu .compare.

Como ordeno nomes alemães como uma lista telefónica?

Peça a variante de colação pelo nome: new Intl.Collator("de-u-co-phonebk"). A parte -u-co- de um identificador de locale seleciona uma colação, e phonebk é a adaptação de lista telefónica alemã, em que ö se comporta como oe, ä como ae e ü como ue. Sobre ["Göbel","Goethe","Godel","Gözde","Gott"], de simples dá Göbel, Godel, Goethe, Gott, Gözde e de-u-co-phonebk dá Godel, Göbel, Goethe, Gözde, Gott. Outras línguas têm as suas variantes: uma lista chinesa pode ser ordenada por pinyin ou por número de traços do mesmo modo.