Todas las entradas de: mkrevuelta
¿Cuál es el mejor algoritmo de ordenación?
Ninguno. Depende de las circunstancias.
Lógicamente, la siguiente pregunta es: ¿Cuál hay que usar en cada caso?
La mejor elección es casi siempre la implementación que viene incluida en el lenguaje que estás usando.
En algunos casos se puede elegir entre las siguientes opciones:
- Ordenación estable. Generalmente con memoria adicional O(N), es decir, proporcional a la ocupada por los datos a ordenar.
- Ordenación no estable. Requiere muy poca memoria adicional, pero no respeta el orden previo de los elementos que se consideran iguales entre sí.
Más detalles en: ordenación estable
y en: notación de la «O grande».
En C++, por ejemplo se puede elegir entre std::sort y std::stable_sort.
En el terreno de la ordenación con poca memoria adicional han destacado varios favoritos a lo largo de la historia: Shellsort (1959), quicksort (1960), heapsort (1964) y más recientemente introsort (1997), que es un híbrido de quicksort, heapsort y la ordenación por inserción.
Mergesort (1945) dominó muchos años en el terreno de la ordenación estable. Su sustituto parece ser Timsort (2002). Se trata también de un híbrido, en este caso de mergesort, la ordenación por inserción y algún truco más.
Hablaré de los pocos casos en los que sí tendría sentido (en mi opinión) usar un algoritmo de ordenación programado a medida. Pero será más adelante ;-)
Mi [primer] libro
¡He escrito un libro!
Bueno, sí, soy un pesado… Lo escribí hace tiempo. Muchos familiares y amigos ya lo han leído e insisten en preguntarme para cuándo el segundo. (Gracias, yo también os quiero ;-)
Pero este blog es nuevo, así que ahí va:
Es una novela corta de ciencia ficción, o más bien un cuento largo. Podéis descargarlo en PDF (gratis) o encargar una copia impresa (pagando) en bubok.
Soy un simple aficionado y cometí algún error que intentaré evitar en el futuro. Concretamente, debo avisaros de que el rollo matemático del principio se puede saltar. No es todo así ;-)
Para terminar, enlazo aquí una perla de la memoria televisiva de España. ¡Qué momentazo!
Project Euler
ProjectEuler.net es un invento magnífico que conocí hace un par de años. Alberga una interesantísima colección de problemas de programación.
Los primeros problemas son relativamente sencillos. Después la dificultad aumenta según se avanza.
Todos los problemas están diseñados para que se puedan resolver con menos de un minuto de procesamiento en un ordenador normal. Muchos de ellos requieren sólo un puñado de microsegundos. Cualquier lenguaje como C o Java con enteros de 64 bits debería bastar. Mucha gente usa otros lenguajes.
En principio los usuarios nuevos sólo tienen acceso a los enunciados de los problemas.
Por cada problema existe un foro en el que los usuarios anteriores han ido compartiendo sus soluciones. Para muchos problemas también hay un resumen en PDF que explica las posibles soluciones.
Pero los usuarios sólo pueden acceder al foro y al PDF de un problema tras haberlo resuelto y haber introducido la respuesta correcta en la página web.
A simple vista podría parecer que esto no tiene mucho sentido. ¿Qué interés puede tener para un usuario que ya ha encontrado la solución? ¡Pues mucho! A menudo hay varias maneras de resolver un problema y no son todas igual de eficientes. El foro y el PDF de un problema contienen pistas vitales para poder encarar los problemas posteriores.
De los cientos de problemas que hay en Project Euler, yo he resuelto 81 hasta la fecha. Gracias a ello he aprendido mucho acerca de combinatoria y programación dinámica, entre otras cosas. Respecto a esto último, por cierto, tengo planeado escribir algún día en este blog.
Aparte de haber resuelto unos cuantos problemas, tengo el orgullo de haber aportado mi granito de arena a Project Euler: me presté voluntario para la confección de los PDF de los problemas 31 y 53.
Por desgracia, Project Euler lleva un tiempo funcionando a medio gas. Los administradores descubrieron que alguien se había colado en su base de datos y cerraron la web completamente. Después la volvieron a abrir pero con «funcionalidad reducida». Es decir, que se puede acceder a los enunciados de los problemas y se puede comprobar si una solución es correcta, pero no hay foros ni resúmenes en PDF.
Replicar aquí los enunciados o dar pistas sobre las soluciones iría en contra de la filosofía de Project Euler, así que me limitaré a enlazar los enunciados…
Problem 31: coin sums (en inglés)
Problem 53: combinatoric selections (en inglés)
… y a facilitar los PDFs con el mismo requisito que se exige en Project Euler, es decir, haber resuelto los problemas previamente:
[..]
Actualización (17 de agosto de 2014): Project Euler ya funciona con normalidad, así que he retirado los PDFs de este blog.
La música que me gusta
Antes de entrar en asuntos técnicos, quiero compartir mis listas de música con vosotros.
Soy un usuario [razonablemente] satisfecho de Spotify. Si vosotros también, podéis acceder a mis listas tecleando spotify:user:comocomocomo en la barra de búsqueda:
Espero que las disfrutéis y os animéis a mandarme las vuestras ;-)
Actialización: Hay una forma más fácil…
¿Cordones? ¿Por qué ese título tan raro?
¿Sabes cómo te atas los cordones de los zapatos?
«¡Naturalmente! Lo hago todos los días» — pensarás.
No, no, no. Ya me imagino que sabes atarte los cordones. Lo que pregunto es si sabes cómo lo haces. ¿Sabrías describirlo paso a paso, con palabras o con dibujos? Eso ya es otra historia… No vale ensayar. No puedes ni mirar tus zapatos. ¿Cómo mueves cada dedo en cada momento?
Si sabes describir cómo te atas los cordones, probablemente es porque has tenido que enseñar a alguien cómo hacerlo.
Con la programación ocurre algo parecido. Tenemos que enseñarle al ordenador cómo hacer tareas que nosotros sabemos realizar. Pero tenemos que describirlas con todo detalle, en un lenguaje muy limitado. El ordenador no sobreentiende nada. A menudo nos encontramos reflexionando duramente para separar los pasos elementales de un proceso que nosotros realizamos de una forma automática, casi inconsciente.
Ahí reside una de las dificultades de la programación. La otra dificultad es que, siguiendo con la analogía, necesitaremos que el ordenador haga todos los nudos marineros conocidos… y alguno más.