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[sup]; lista[sup] = 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?
