Además de ayudar a resolver dudas sobre programación, a veces Stackoverflow también sirve para echar unas risas. Pero sólo si tienes un sentido del humor un tanto especial, y te hacen gracia las discusiones prácticas sobre la eficiencia de los algoritmos para el emparejamiento de calcetines.

Y es que, como bien explica el usuario Amit Gross en su pregunta, usar una búsqueda simple, seleccionando un calcetín e iterando sobre la pila de calcetines restantes en busca de su pareja, es una operación muy costosa, que requeriría iterar sobre n/2 * n/4 = n²/8 calcetines de media.

La respuesta más votada sugiere utilizar un particionado recursivo basándose en un hash, como hace, por ejemplo, SQL Server cuando trabaja con grandes volúmenes de datos. Con este algoritmo clasificaríamos los calcetines en distintas pilas según su color, y distribuiríamos estos calcetines en pilas más pequeñas basándonos en otros criterios, como el dibujo, hasta tener pilas lo suficientemente pequeñas para poder procesarlas visualmente rápidamente.

No es que fuese una asignatura que me disgustara especialmente en su día, pero lo que sí es cierto es que nunca pensé que una clase sobre algoritmos pudiera ser tan entretenida como en estas danzas húngaras creadas por la Sapientia University, de Rumania.

En el bubble sort, por ejemplo, cuya coreografía podéis ver a continuación, se compara cada uno de los elementos de la lista con el siguiente, intercambiándose si el primero es mayor que el segundo. El algoritmo se repite hasta que no es necesario hacer ningún otro cambio.

En su cuenta de YouTube podéis ver otros ejemplos, como el select sort, el shell sort y el insert sort.