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

11 comentarios en “ordenando a montones”

  1. Como dirían en el IRC… No vamos a hacerte los deberes, que la última pregunta canta un poco… };)

    En cuanto termine los exámenes le echo un ojo. ¡Cuídate, y cuida del Chema!

  2. las 1ras son ejercicios faciles y me dejaron contento porq las estaba haciendo mentalemente mientras leia el post …
    Pero la 4ta me dejo boquiabierto y creo q tengo un ToDo para este finde … 😀

    Saludos

  3. buenas crases!

    Penyaskito, acaso insinuas que estoy utilizando a mis bienamados lectores? Te sientes un lector-objeto? Y si es asi, de que clase eres instancia? }:)

    En principio, tengo al menos una solucion al problema antes de plantearlo… En el futuro podemos probar a poner problemas para los que no sepa si hay solucion, si te mola }:D

    Bruno: me alegro que te guste! Los dos primeros son mas que nada para ayudar a repasar conceptos de ordenacion y rendimiento de las distintas opciones que puedes elegir (ya sabes que hay mas de una algoritmo, que el rendimiento depende del caso, etc…) El tercero implica mas que nada pensar: cuanto de esto puedo meter en memoria si quiero usar mi algoritmo? Y el cuarto… digamos que requiere pensar las cosas “de un modo distinto” }:)

  4. Hola Ricardo!

    Me parece muy interesante lo que comentas, sobre todo el caso en el que la memoria es limitada, porque el rendimiento del algoritmo de ordenación dependerá mucho entonces del patrón de acceso a datos que esté utilizando el algoritmo. En este caso, las ordenaciones que teóricamente son más rápidas pueden no serlo en el caso real (por ejemplo se me ocurre que el heapsort en los casos 3 y 4 puede no funcionar muy bien…)

    A ver si le puedo dar una pensada y te comento lo que se me ocurre al respecto 😉

    Saludos!

  5. Hola panda de señori@s lectores. Si yo, que el último programa que hice era uno de rutas de bares (primero cerveza en este, luego calimotxo en este otro, luego cubata, luego chupito y luego borrachito) lo he podido sacar en 3 horas, vosotros tenéis que sacarlo ya!

    Además, estaba borracho y le dediqué unas horitas por la noche.

    Pista: ¿cuantos amarracos se necesitan para contar los juegos? 1 hombre, 1 voto.

  6. mmm… muy parada veo la cosa por aqui. Si nadie se anima a dar una solucion, que lance al menos alguna duda para ver que tal va esa orientacion! }:)

    P.S. y por cierto, Chema lo saco por la noche en mi casa y sin pistas, eso es completamente cierto… y es de IT! }:P

  7. Un par de dudas… En el tercer caso, el flujo de salida sólo sirve para escribir datos “finales”? Es decir, ¿sólo puedes escribir datos que ya están ordenados, o se pueden escribir datos temporales?

  8. Por cierto, voy a proponer una posible solución para el cuarto problema:

    Construimos un arbol en el que los nodos de primer nivel (ordenados) representan el byte de más alto nivel de los números a ordenar. Debajo de este almacenaremos los dos bytes restantes de cada número en cuestión (ya que ocupan 3 bytes máximo). Y los almacenamos desordenados en principio.

    9999999 / 255 = más de 39000 entradas, pero menos de 40000. Si tenemos en cuenta que cada entrada del nivel inferior ocupa 2 bytes, tenemos 80000 bytes en total para cada nodo. Como tenemos 255 nodos, si multiplicamos, tendremos 20400000 bytes que ocupa la estructura. Es un poco justito, pero cabe.

    Ahora bien, si lo que hacemos es construir un arbol de tres niveles, uno por byte, y las inserciones las hacemos ordenadas, basándonos directamente en el valor de cada byte, podremos ordenarlos en O(n * k), pero no he calculado el número de bytes que ocuparía… No ando con mucho tiempo y se me acaba de ocurrir… Luego lo pienso con más calma.

  9. Después de darle a la cabeza y darme cuenta de que lo que he dicho antes es una estupidez… Ya tengo la solución, y ocupa exactamente 10.000.000 bits.

    ¿Hasta ahí vamos bien? ¿Digo la solución ya?

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *