Como algunos de vosotros sabreis, esta semana tengo a Chema de visita en casa, asi que escribir se nos esta haciendo mucho mas dificil (porque claro, la fiesta y los blogs no son muy compatibles). Sin embargo, tenia pensado empezar a anyadir mas tipos de problemas esta semana, asi que… alla vamos!
En este problema vamos a intentar subir un poco el nivel… de abstraccion, quiero decir. Vamos a desempolvar un poco esos libros de algoritmos y ver un problema muy basico: la ordenacion. Pero claro, esto es programancia101 y aqui no podemos ordenar cualquier cosa. Al igual que en otras ocasiones, vamos a plantear este problema por fases:
- La primera parte seria algo como: sabrias decir cual es la forma mas rapida de ordenar diez mil (10.000) numeros? Que tiempo (aproximadamente) llevaria hacerlo en tu ordenador?
- La segunda, continuando con la idea: cual es la forma mas rapida de ordenar un millon (1.000.000) de numeros? Que tiempo (aproximadamente) llevaria hacerlo en tu ordenador? Se comporta de forma lineal con el caso anterior? Por que?
- La tercera, partiendo de este segundo caso: imaginemos que la maquina en la que vamos a ordenar nuestro millon de numeros solo tiene 2 megabytes de memoria, una cantidad ilimitada de disco duro y que nuestros numeros son enteros sin signo de 32 bits. Supon que disponemos de un flujo de entrada para leer los enteros de forma secuencial y un flujo de salida en el que podemos escribir enteros, ambos accesibles mediante las funciones/metodos:
// Devuelve el siguiente entero a ordenar
int LeerSiguiente();
// Escribe el entero en el stream de salida
void Escribir(int numero);
NOTA: a efectos de complejidad, podemos suponer que las llamadas a estas funciones/metodos son de orden constante
Cual seria la mejor forma en este caso? - Y finalmente, la cuarta, rizando el rizo: imaginemos que los numeros anteriores proceden de un listado sin repeticiones de numeros de telefono de exactamente 7 digitos y que NO tenemos acceso a disco (y si, seguimos teniendo solo 2 megabytes de memoria): serias capaz de ordenarlos de la forma mas rapida posible?
Como siempre, estais invitados a comentar vuestras soluciones en los comentarios, o bien publicarlas en vuestro blog y dejar un enlace! }:)
NOTAS: Como orientacion de dificultad: las dos primeras partes deberian ser sencillas para un nivel basico/medio y repasando un poco algo de algoritmos de ordenacion. La tercera es un poco mas intermedia y la cuarta requiere un poco mas de pensar (asi que la he puesto como avanzada).