Mis algoritmos de ordenamiento – Parte I: Funny Sort
Intro
La convivencia de las palabras “pelotudo” y “programador” en una misma frase parece en sí algo redundante, pero no lo es totalmente, no porque no sea cierto que los programadores sean boludos, sino porque hay boludos que no saben programar.
Por eso esta sección es ATP (Apta para Todos los Pelotudos), ya que no está dedicada exclusivamente a expertos informáticos o a programadores. Alcanza con ser un poco boludo para poder disfrutarla.
Presentación
Como anuncié en la entrega anterior de esta misma sección, voy a presentarles hoy el primero de los revolucionarios algoritmos de ordenamiento que yo mismo he inventado. Esto es el fruto de mis más de 10 años de investigación en el campo de las ciencias de la computación.
Funny Sort
Sin dudas (no lo digo porque lo haya inventado yo) se trata de un algoritmo realmente interesante, dadas su velocidad y su complejidad espacial. Para ambas presenta una gran performance: O(n) para un tamaño n, lo que, sin dudas, es maravilloso. Funcionalmente, el algoritmo es tan simple como divertido, ya que recibe un arreglo con los elementos a ordenar y lo único que hace es intercambiar sus elementos entre sí aleatoriamente, para lo cual recorre el arreglo entero, con costo O(n), y como el costo de generar un número aleatorio (en realidad, pseudoaleatorio) es constante, tendremos: O(n)+n.O(1) = O(n)+O(n) = O(2n) = O(n), siendo n la cantidad de elementos a ordenar.
Como habrán intuido, queridos boludos programadores, el resultado de este algoritmo es divertidísimo: ¡ningún elemento queda en la posición que esperaríamos que quede!
Pseudoexplicación del pseudocódigo
Bueno, el algoritmo recibe dos parámetros que son los dos arreglos, el original y el que devolveremos como resultado. Luego de inicializar las variables genera los n-1 números aleatorios, siendo n el tamaño total del arreglo a ordenar.
Después llena el arreglo que va a devolver. ¡Una boludéz!
Ejemplito
Para que se entienda mejor, veamos un simple y claro ejemplito gráfico. Utilizaremos para esto un pequeño arreglo de 6 elementos (n = 6):
Supongamos que el Funny Sort recibe para ordenar un arreglo como el de la figura 1.a. En este caso el algoritmo generará n números aleatorios entre 0 y 5 (n-1 = 6-1 = 5) con costo n.O(1) = O(n). Y creará un nuevo arreglo con los nuevos números generados (figura 1.b).
Luego, simplemente recorrerá el arreglo original y colocará cada uno de los elementos que lo componen en el arreglo resultante, donde la posición final de cada número estará indicada por el arreglo de números aleatorios. En nuestro ejemplo, el arreglo resultante sería el de la figura 1.c.
Como podemos apreciar, el arreglo resultante no tiene el orden que uno esperaría de cualquier algoritmo de ordenamiento, lo que lo convierte en el algoritmo más loco y divertido del mundo.
Contacto
Si sos un auténtico boludo (programador o no) podés contactarte con Bill Gay a través de la sección de contacto de la revista o enviando un mail a [email protected]. Pueden pedirle a Bill lo que quieran: cursos sobre algún lenguaje en particular, datos históricos, recomendaciones para programar o para optar entre un lenguaje u otro, lo que sea, el chabón es re groso y les va a contestar todo lo que quieran saber.
Flores Negras N°40
Intro
La convivencia de las palabras “pelotudo” y “programador” en una misma frase parece en sí algo redundante, pero no lo es totalmente, no porque no sea cierto que los programadores sean boludos, sino porque hay boludos que no saben programar.
Por eso esta sección es ATP (Apta para Todos los Pelotudos), ya que no está dedicada exclusivamente a expertos informáticos o a programadores. Alcanza con ser un poco boludo para poder disfrutarla.
Presentación
Como anuncié en la entrega anterior de esta misma sección, voy a presentarles hoy el primero de los revolucionarios algoritmos de ordenamiento que yo mismo he inventado. Esto es el fruto de mis más de 10 años de investigación en el campo de las ciencias de la computación.
Funny Sort
Sin dudas (no lo digo porque lo haya inventado yo) se trata de un algoritmo realmente interesante, dadas su velocidad y su complejidad espacial. Para ambas presenta una gran performance: O(n) para un tamaño n, lo que, sin dudas, es maravilloso. Funcionalmente, el algoritmo es tan simple como divertido, ya que recibe un arreglo con los elementos a ordenar y lo único que hace es intercambiar sus elementos entre sí aleatoriamente, para lo cual recorre el arreglo entero, con costo O(n), y como el costo de generar un número aleatorio (en realidad, pseudoaleatorio) es constante, tendremos: O(n)+n.O(1) = O(n)+O(n) = O(2n) = O(n), siendo n la cantidad de elementos a ordenar.
Como habrán intuido, queridos boludos programadores, el resultado de este algoritmo es divertidísimo: ¡ningún elemento queda en la posición que esperaríamos que quede!
Pseudoexplicación del pseudocódigo
Bueno, el algoritmo recibe dos parámetros que son los dos arreglos, el original y el que devolveremos como resultado. Luego de inicializar las variables genera los n-1 números aleatorios, siendo n el tamaño total del arreglo a ordenar.
Después llena el arreglo que va a devolver. ¡Una boludéz!
Ejemplito
Para que se entienda mejor, veamos un simple y claro ejemplito gráfico. Utilizaremos para esto un pequeño arreglo de 6 elementos (n = 6):
Supongamos que el Funny Sort recibe para ordenar un arreglo como el de la figura 1.a. En este caso el algoritmo generará n números aleatorios entre 0 y 5 (n-1 = 6-1 = 5) con costo n.O(1) = O(n). Y creará un nuevo arreglo con los nuevos números generados (figura 1.b).
Luego, simplemente recorrerá el arreglo original y colocará cada uno de los elementos que lo componen en el arreglo resultante, donde la posición final de cada número estará indicada por el arreglo de números aleatorios. En nuestro ejemplo, el arreglo resultante sería el de la figura 1.c.
Como podemos apreciar, el arreglo resultante no tiene el orden que uno esperaría de cualquier algoritmo de ordenamiento, lo que lo convierte en el algoritmo más loco y divertido del mundo.
Contacto
Si sos un auténtico boludo (programador o no) podés contactarte con Bill Gay a través de la sección de contacto de la revista o enviando un mail a [email protected]. Pueden pedirle a Bill lo que quieran: cursos sobre algún lenguaje en particular, datos históricos, recomendaciones para programar o para optar entre un lenguaje u otro, lo que sea, el chabón es re groso y les va a contestar todo lo que quieran saber.
Flores Negras N°40