Mientras Arcadio elegía el regalo de Úrsula, sentía que la cabeza le daba vueltas de tanto analizar, caso por caso, todas las opciones que se le presentaban. La búsqueda exhaustiva puede, como ya lo estudiamos, encontrar la mejor solución, pero en un tiempo inaceptable para Arcadio, un tiempo exponencial. ¿Sería posible encontrar un regalo que fuera tan parecido al regalo ideal pero que no se notara la diferencia? Una vez decidido a ignorar el análisis caso por caso de todas las opciones, Arcadio asignó a los objetos una prioridad: qué tanto le gustaría a Úrsula cada objeto. Posteriormente, con los objetos "calificados" en esta forma, procedió a ordenarlos de acuerdo con este criterio y a comprarlos en orden de mayor a menor importancia hasta agotar su dinero.
El problema de ordenar una lista de objetos según algún criterio que utiliza Arcadio al final de su aventura comercial, es uno de los problemas más importantes que hay en computación. Muchas de las tareas que ejecutan las computadoras necesitan apoyarse en algoritmos de ordenamiento. Cada uno de los objetos que se quieren ordenar tiene asociado uno o más valores numéricos, como pueden ser el precio, el tamaño, el peso, etcétera, y se requiere ordenarlos apegándose a alguno de estos parámetros. Para el problema algorítmico se vuelven irrelevantes los otros parámetros y, de hecho, cualquier otra característica de ellos también, como podría ser su color. A veces se requiere ordenarlos de mayor a menor y, en otras, al revés; el mismo algoritmo funciona en ambos casos. De este modo, definimos formalmente: en el problema de ordenamiento, la entrada es una lista de números, y se pide que la salida sea una lista con los mismos números, pero ordenados de menor a mayor. Por ejemplo, si la entrada es [17, 23, 17, 5], la salida debe ser [5, 17, 17, 23].
Un algoritmo de búsqueda exhaustiva para este problema sería inaceptable; correría en un tiempo peor que exponencial. Si se cuenta con una lista de tres números por ordenar crecientemente, por ejemplo [23, 17, 5], las posibles maneras de ordenar la lista son 3 × 2 × 1 = 6; hay tres formas diferentes de elegir el primer elemento de la lista. Por cada una de ellas existen dos para el siguiente, puesto que no se puede repetir el primero y, finalmente, por cada una de las elecciones de los primeros dos elementos hay sólo una opción para el último, pues ya sólo queda exactamente uno por incluir.
En este ejemplo, los posibles ordenamientos son: [23, 17, 5], [23, 5, 17], [17, 23, 5], [17, 5, 23], [5, 23, 17] y [5, 17, 23]. Sólo una de estas opciones, la última, de hecho, tiene la lista ordenada de menor a mayor. Se usará n para designar el tamaño de la lista, es decir, el número de elementos de la lista por ordenar. Con n = 5, tenemos 5 × 4 × 3 × 2 × 1 = 120.
En general, se tiene la función factorial que ya había sido presentada: el número de posibles ordenamientos es n!, lo cual es mucho peor que el problema inicial de Arcadio.
Vale la pena recordar que esta función crece más rápido que cualquier función exponencial de la forma Cn. El número de opciones de compra para n objetos sólo duplica el de n − 1, pero el número de ordenamientos posibles es n veces el de n − 1.
Afortunadamente, hay mejores maneras de resolver el problema, ya que no hace falta analizar todas las opciones, lo que, hasta donde sabemos, es imposible en el caso del problema de determinar los objetos a comprar. Más adelante se verán algunos de los algoritmos de ordenamiento más eficientes.
