Alba on Tech

Talking about technology

Kata: Ordenar un array ¡sin bibliotecas ni internet!

Hoy en día estamos muy acostumbrados a contar con infinidad de bibliotecas que nos ofrecen soluciones a muchos de los problemas de programación más comunes. Esto es algo maravilloso, que permite centrar el desarrollo en los problemas específicos de una aplicación, y no tener que reinventar la rueda. Pero ¿por culpa de estas facilidades hemos olvidado cómo hacer las cosas nosotros mismos?.

La kata de hoy consiste en ordenar un array de enteros. Es una tarea muy sencilla. Python te da “sorted”, java te da “Collections.sort()”, etc, etc. Además, internet, o cualquier libro de fundamentos de la programación, están llenos de ejemplos en cualquier lenguaje de cómo hacer un quick sort, una ordenación por árbol binario, etc.

El reto de hoy es no recurrir a ninguna biblioteca de ordenación, ni mirar internet para recordar cómo era aquello del pivote… El reto es escribir desde cero un método que reciba un array de 100 enteros, y los devuelva ordenados, y escribirlo por tus propios medios. Lo ideal sería que empezases con papel y boli, diseñando cómo va a funcionar tu algoritmo, y luego lo codifiques, ¡y pruebes que funciona!

¿Qué tal te ha salido? ¿Has sido capaz de hacer algo mejor que la ordenación por burbuja?

Y recuerda, no se trata de un concurso. Se trata de una kata. Practica y mejora. Siempre

Advertisements

23 February, 2012 - Posted by | Kata, Programación

8 Comments »

  1. Ahi va una en C++/Qt, me sirvió como escusa para recordar cosas de Qt 😛

    Comment by Andrei Antoukh | 25 February, 2012 | Reply

  2. Buenas,

    Mi propuesta es una que he bautizado “clases de equivalencia” pero imagino que tendrá un nombre más apropiado[1]. El bubblesort tiene una complejidad algorítmica tipo n2 seguro pero haciendo pruebas con éste (que emplea internamente el bubblesort), tiene una complejidad algorítmica prácticamente lineal (yuhu!).

    El esquema visual del algoritmo aquí: http://dl.dropbox.com/u/3488882/kata_pabloruiz.jpg
    El código en sí escrito en python aquí: http://pastebin.ca/2121530
    La gráfica de complejidad algorítmica aquí: http://dl.dropbox.com/u/3488882/kata_compalgoritmica.png

    Cuando paso a un array de 100000000 números, el tiempo se me dispara pero imagino que por otras razones, no por el algoritmo en sí.

    [1] No es un divide y vencerás porque no parte el problema en n subproblemas de idéntica naturaleza.

    Comment by Pablo Ruiz Múzquiz | 25 February, 2012 | Reply

    • Pablo, ¿qué pasa si cada número pertenece a una clase de equivalencia distinta? Entonces, dividirlos por clases de equivalencia no te sirve de nada y el número de operaciones crece con n^2 (bubblesort).

      Según la gráfica, el tiempo (que no sé si es lineal con el número de operaciones) crece linealmente con n. Esto no creo que se deba a una eleccion “adecuada” del array de origen. Supongo que los números los has elegido de forma aleatoria o pseudoaleatoria.

      No consigo pensar una razón en concreto, pero creo que ese algoritmo tiene que ser de orden n^2, ya que en el peor de los casos es de ese orden.

      Saludos!

      Martxelo

      Comment by Martxelo | 29 February, 2012 | Reply

      • La clase de equivalencia está elegida adrede. Es parte del problema saber qué tipos de números vas a recibir. El enunciado dice 100 números aleatorios y yo he elegido 100 del 0 al 99 (con el random.shuffle de python). Si hubieran sido 100 números de otro tipo, yo tendría que saberlo (puedo leer el array primero, que es O(n)) y elegir la mejor clase de equivalencia.

        En el caso peor, que todos los números pertenezcan a una clase de equivalencia, ¡es el caso mejor! porque el propio recorrido y colocación en sus “cajones” los estaría ordenando 🙂
        En el caso realmente peor, que todos los números pertenezcan a UNA clase de equivalencia, entonces he elegido mal mi clase de equivalencia y la pregunta no ha lugar.

        Entiendo tu sensación de que el algoritmo es “en esencia” de O(n2) porque el caso peor es O(n2) pero el algoritmo tiene la capacidad de definir la clase de equivalencia óptima y esto le confiere un O <= O(n2) en la práctica real.

        Pablo ¿cuándo podemos investigar nuestras propuestas? Me he autoimpuesto una censura en Internet sobre esto pero me pica la curiosidad.

        Comment by Pablo Ruiz Múzquiz | 29 February, 2012

    • Se me ha olvidado pero la primera pregunta debería ser ¿qué pasa si todos los números son de una clase de equivalencia distinta o todos son de la misma clase de equivalencia?

      Martxelo

      Comment by Martxelo | 29 February, 2012 | Reply

    • Tienes razón. He encontrado esto:

      http://en.wikipedia.org/wiki/Bucket_sort

      Y ahí dice que es de orden n cuando los elementos están uniformemente distribuidos, que es el caso más habitual. Lo he sacado de aquí:

      http://en.wikipedia.org/wiki/Sorting_algorithm#Summaries_of_popular_sorting_algorithms

      Por cierto, en este último link sí que dice que el bucket sort es de tipo divide y vencerás. En castellano lo llaman ordenamiento por casilleros.

      Si lo has hecho por tu cuenta, te felicito. ¡Has descubierto por ti mismo uno de los algoritmos de ordenación más eficientes que existe!

      Martxelo

      Comment by Martxelo | 29 February, 2012 | Reply

      • 🙂

        ¡Bucket sort! Pues sí, se parece mucho mucho mucho. De hecho, incluso usé el concepto de “bit más significativo” (véase la foto de la pizarra) que tiene todo el sentido para que la clase de equivalencia sea útil para ordenar. Lo de divide y vencerás fue mi estrategia inicial para pensar el algoritmo pero tras llegar a él decidí que NO era divide y vencerás porque pensé que tenían que ser problemas IGUALES (la wikipedia dice: “into two or more sub-problems of the same (or related) type” related… hmmm…). Ahí me equivoqué.

        En cualquier caso, aunque lo hice por mi cuenta, he estudiado una carrera de informática y está claro que estoy “entrenado” para recurrir a conocimiento de este tipo, no lo veo tan relevante (y la carrera de físicas algo ayuda, claro). Lo que sí me ha gustado es ver que fui directo a resolverlo para O(n) y que no me llevó mucho.

        Estas katas molan 🙂
        ¿Y tú, te peleaste con ella?

        Comment by Pablo | 29 February, 2012


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: