ordenando a montones

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).

testeando en el cuarto de baño

(y pondria lo de «testeando» entre comillas porque no se como traducir «bonitamente» el anglicismo, pero es que entonces suena sospechoso)

Ya comente que una de las cosas que queria poner en programancia101, aparte de problemas, son recomendaciones de «buenas practicas». En este caso, no es que vaya a decir que testear es una buena idea, eso lo sabeis todos (verdad?)… solo queria compartir este programa que usamos en Google para dar a conocer buenas practicas para la fase de pruebas entre los desarrolladores. La idea basica es: coloca la informacion donde TODOS puedan leerla }:)

Asi surgio la idea de «Testing On The Toilet» (lo que viene a traducirse en español como el titulo de este articulo). Si colocamos semanalmente una hoja con problemas sobre testing en uno de los lugares mas visitados de la oficina, la gente acaba por leerla. Desde hace unos dias, estos bonitos ejemplos de cultura Googley estan disponibles para descarga desde el Google Testing Blog (solo en ingles, eso si)

Asi que ya sabes: bajatelo, imprime y… difunde el conocimiento alla donde sea necesario! }:)

expansiones infinitas

Para los que ya le han echado un ojo al problema anterior y han leido los comentarios sobre las expansiones (hey! recuerdo que si no habeis probado sin leer pistas primero es hacer trampa!) os dejo otro pequeño puzzler sobre el tema.

Imaginemos un trocito de codigo como:

double result1 = 3.65d + 0.05d;
float result2 = 3.65f + 0.05f;

Console.WriteLine(result1 == 3.7d);
Console.WriteLine(result2 == 3.7f);
Console.WriteLine(result1 == result2);

¿Sabríais decir cuál será la salida que obtendremos al ejecutar?