Volvemos con un nuevo acertijo en nuestra serie ¿De dónde es este código?, aunque esta vez va a ser algo distinto, ya que no se trata de un proyecto del mundo del Software Libre, sino de un algoritmo clásico.
Por tanto, esta vez no traemos código fuente propiamente dicho, sino un pseudocódigo que seguro que a más de uno le sonará de sus primeros años de estudios de informática.
El código
function miAlgoritmo(lista, limSup, limInf)
{
pivote = lista[limSup];
i = limInf - 1;
j = limSup;
if (i < j)
return;
do
{
while (lista[i] < pivote)
i++;
while (lista[j] > pivote)
j--;
if (i < j)
{
swap = lista[i];
lista[i] = lista[j];
lista[j] = swap;
}
} while (i < j)
swap = lista[i];
lista[i] = lista[limSup];
lista[limSup] = swap;
miAlgoritmo(lista, limInf, i - 1);
miAlgoritmo(lista, i + 1, limSup)
}
El reto
Una vez acertado el nombre del algoritmo, lo que seguramente os resulte muy fácil, hay otras preguntas acerca del mismo para las que buscamos vuestra respuesta.
-
¿Cuál es el orden de complejidad promedio de este algoritmo? ¿Y en el peor de los casos? ¿De qué depende obtener uno u otro?
-
¿Qué dos características de la versión que hemos publicado en pseudocódigo hacen que sea más lento de lo que podría de estar optimizado?
-
Antes de la aparición de este algoritmo, había otros que solucionaban el mismo problema por fuerza bruta, sin divide y vencerás ni ninguna otra estrategia. ¿Qué complejidad computacional tenían?
-
¿Serías capaz de decir algún software real que implemente este algoritmo?
-
Y la más inquietante, ¿qué tiene que ver la foto que encabeza el artículo con el algoritmo en cuestión?
Solución al anterior reto
Aunque la mayoría de participantes acertaron casi todas las preguntas de la anterior entrega, no está de más recordarlas para quien le faltase alguna.
Ese código Ruby embebido (erb, Embedded RuBy) cuyo aspecto tanto desagradó a los observadores debido a su CSS empotrado, se trataba de la vista del apartado de diagramas de Gantt de Redmine, un conocido software de gestión de proyectos. Y de hecho, la visualización del código es una parte de la propia herramienta: el acceso a ficheros del repositorio.
La empresa australiana BitBot Software, agradecida por la utilidad que el uso de Redmine les había supuesto, decidió revertir directamente en la comunidad ofreciendo sin coste alguno el servicio Hosted Redmine, ya que la mayoría de los servicios gratuitos de hosting ofrecen lenguajes como PHP, pero no Ruby.
En cuanto al fork generado por descontento con la gestión del proyecto, se trata de Bluemine, que para evitar problemas por el parecido en el nombre finalmente se rebautizó como ChiliProject.
