Ordenar y quitar duplicados de una lista sin sorpresas

Ordenar y quitar duplicados parecen las dos cosas más sencillas que se le pueden hacer a una lista, y por eso los resultados están mal tan a menudo sin que se note. Las dos se apoyan en una comparación, y no hay una única respuesta a qué hace que dos líneas sean iguales o que una vaya antes que otra.

El orden lexicográfico no es el orden numérico

La comparación de texto por defecto recorre dos cadenas carácter a carácter, compara puntos de código y se detiene en la primera diferencia. Nada en ella sabe qué es un número.

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

img10.png acaba en segundo lugar porque en el cuarto carácter 1 (U+0031) es menor que 2 (U+0032), y la comparación termina ahí. Esa misma regla coloca la versión 1.10 antes que la 1.9 y muestra una carpeta de capturas de pantalla en un orden distinto al que se tomaron.

La comparación numérica también arregla los negativos: lexicográficamente, -10 cae entre -1 y -2, porque un signo menos no es más que otro carácter con su punto de código.

Mayúsculas antes que minúsculas y otras sorpresas de los puntos de código

En ASCII, las mayúsculas ocupan del 65 al 90 y las minúsculas del 97 al 122, así que toda mayúscula se ordena antes que toda minúscula.

Los dígitos quedan por debajo de todas las letras, el espacio (32) por debajo de todo carácter imprimible, y una línea vacía por debajo de eso, así que un orden ascendente junta arriba del todo las líneas en blanco y las que empiezan por espacio, y un orden descendente las junta abajo.

Los espacios finales son la versión invisible del mismo problema: apple y apple se ordenan una junto a otra y parecen un duplicado que se niega a desaparecer. El espacio de no separación (U+00A0) es peor, porque se dibuja igual que un espacio normal pero se ordena por encima de todas las letras, y lo mismo pasa con el retorno de carro que queda cuando un archivo de Windows se divide solo por saltos de línea. Si dos líneas parecen idénticas y aun así no se juntan, busca caracteres ocultos.

La misma lista se ordena distinto en dos países

El orden por punto de código también coloca todos los caracteres acentuados después de todos los no acentuados. Zürich se ordena después de Zzz, y Ärger después de zebra. Ningún idioma ordena su propio alfabeto así. La colación consciente de la configuración regional compara según las reglas del idioma, y esas reglas no coinciden entre sí.

En JavaScript esto vive en 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

El mismo objeto cubre los problemas anteriores. { numeric: true } compara las rachas de dígitos como números, que es el orden natural, y sensitivity fija qué cuenta como diferencia: "base" ignora la caja y los acentos, "accent" ignora solo la caja y "case" ignora solo los acentos. Omitir la configuración regional usa la que tenga puesta la máquina, que es como el mismo código devuelve dos órdenes distintos en dos portátiles. Indica la configuración regional cuando la salida tenga que coincidir en todas partes.

Qué duplicados cuentan como duplicados

La eliminación de duplicados está tan bien definida como lo esté la prueba de igualdad que hay detrás. Toma cinco líneas que se muestran todas como la palabra cafe con acento agudo:

Cuatro reglas razonables dan cuatro respuestas distintas:

Ninguna está mal; responden a preguntas distintas. La normalización importa más de lo que parece, porque el texto que viene de nombres de archivo de macOS suele llegar descompuesto (NFD) y el que viene de Windows y de formularios web llega compuesto (NFC), así que una lista pegada desde dos fuentes se llena de gemelos invisibles. NFKC va más lejos y pliega los caracteres de compatibilidad, como la ligadura fi, en sus equivalentes simples.

Por convención gana la primera aparición, así que si la copia desordenada se pegó primero, es la que sobrevive. Y quitar duplicados es una petición distinta de encontrar los elementos únicos: la herramienta de eliminar líneas duplicadas deja uno de cada, mientras que el conjunto de únicos de la herramienta de frecuencia de listas es el grupo, más pequeño, de elementos que aparecen exactamente una vez.

Estabilidad y ordenar por dos claves

Una ordenación estable garantiza que las entradas que el comparador considera iguales conservan el orden que tenían en la entrada. Eso es lo que hace que funcione ordenar por varias claves en pasadas sucesivas: ordena primero por la clave menos importante y después por la más importante. Ordenar por nombre y después por departamento da los departamentos en orden, con los nombres ordenados dentro de cada uno. Una ordenación inestable deshace la primera pasada mientras hace la segunda, y el resultado parece casi correcto, que es peor que parecer incorrecto.

Invertir tiene la misma pega, porque dar la vuelta a una lista ordenada también invierte cada grupo empatado. Usa la herramienta de invertir listas cuando lo que quieras sea dar la vuelta al orden entero, no como atajo para una ordenación descendente.

Las implementaciones difieren. Array.prototype.sort de JavaScript solo está obligado a ser estable desde ES2019; antes de eso V8 usaba un quicksort inestable a partir de cierto tamaño de array, así que el mismo código se comportaba distinto con diez elementos y con diez mil. El sorted de Python es estable, y el sort de GNU no lo es salvo que se le pase -s.

Barajar no es un tipo de ordenación

El barajado de una línea, list.sort(() => Math.random() - 0.5), está sesgado. Una ordenación da por hecho que su comparador describe un orden coherente, y solo pregunta por el subconjunto de pares que necesita su algoritmo. Un comparador que saca un número nuevo en cada llamada rompe esa suposición, así que el resultado depende del algoritmo y de la longitud del array: los elementos tienden a quedarse cerca de donde empezaron, y algunas permutaciones salen muchísimo más a menudo que otras.

Un barajado correcto usa Fisher-Yates, recorriendo desde el final e intercambiando cada elemento con otro elegido de forma uniforme entre él mismo y los anteriores:

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]];
}

La variante rota más habitual usa Math.random() * list.length dentro del bucle, sacando de todo el array cada vez. Eso da n elevado a n secuencias de extracción igual de probables, que no se divide de forma exacta entre las n factorial ordenaciones posibles, así que algunas ordenaciones salen más a menudo.

La aleatoriedad y la ordenación se pueden combinar correctamente dando a cada elemento una clave aleatoria de entrada y ordenando por esa clave, porque así el comparador se mantiene coherente. El fallo está en tirar el dado dentro de la comparación.

En qué orden van los pasos

La mayoría de los problemas con listas vienen de hacer las operaciones correctas en el orden equivocado.

1. Desenvuelve primero. Una lista copiada de código llega como "apple",; las comillas y la coma forman parte de la cadena, así que nunca coincide con apple. La herramienta de desenvolver elementos de lista las quita.
2. Recorta y normaliza, para que la igualdad signifique lo que crees que significa.
3. Quita los duplicados, con la regla de coincidencia elegida a propósito y no aceptada por defecto.
4. Ordena. La herramienta de ordenar líneas cubre el orden de texto, numérico, por longitud y aleatorio; añade una configuración regional para datos con acentos.
5. Cambia la forma al final. La herramienta de agrupar elementos de lista corta el resultado en lotes de tamaño fijo para un límite por petición, y la de rotar listas desplaza todo sin cambiar el orden interno.

Quitar duplicados antes de recortar deja atrás casi duplicados, y ordenar antes de quitar duplicados solo ordena filas que están a punto de tirarse.