Ellen Feiss

¿Recuerdas a Ellen Feiss? Esta chica, de aire desgarbado y mirada lánguida, representó uno de los primeros fenómenos audiovisuales de masas en Internet cuando aún no había nacido YouTube ni, por supuesto, Google Videos.

Feiss, joven estadounidense nacida en 1987, contaba con 14 añitos cuando fue seleccionada para interpretar uno de los anuncios televisivos de la campaña publicitaria «Switch» de Apple, ideada por el director de documentales Errol Morris. Dicha campaña se componía de una batería de anuncios en los que aparecían personas de diversas edades, sexo y condición contando las experiencias (reales) que les hicieron maldecir su PC. El objetivo era transmitir situaciones auténticas que dejaran al PC, y sobre todo al sistema operativo Windows, por los suelos con el fin de cambiar y comprar un Mac.

Hubo bastantes anuncios con variedad de personajes y diversidad de problemas que provocaban el cambio, pero Ellen Feiss revolucionó al personal con su historia de cómo se había colgado el PC de su padre mientras trabajaba con él y su ya afamado «beep, beep, beep».

http://www.youtube.com/watch?v=l2-UuIEOcss

El icono cultural y geek en el que se convirtió Ellen Feiss vino alimentado por las malas lenguas que aseguraban que, en el rodaje de aquel anuncio, la chiquilla aparecía bajo los efectos de las drogas. El estilo de hablar desgalichado, los chocantes silencios, la sensación de ausente, los gestos absurdos y, sobre todo, la mirada perdida de unos ojos enrojecidos y medio cerrados fueron los desencadenantes de aquel rumor, que se extendió como la pólvora en forma de meme a lo largo y ancho de Internet. El chisme fue desmontado posteriormente por la propia Feiss, aduciendo el argumento de la ingesta de un medicamento (Benadryl) para la alergia que padece y el cansancio ocasionado por ser ella la última en rodar.

Lo cierto es que esta muchacha era compañera de clase de Hamilton Morris, hijo del director de los anuncios de la promoción que, un día, al salir de clase, invitó a unos cuantos de sus amigos a ver cómo rodaba su padre. Al estar allí, se les pidió a varios de ellos que hicieran una prueba rodando un spot, y tanto Ellen como Hamilton (el hijo del jefe, ¿sospechoso?) fueron escogidos. Como dijo ella en una posterior entrevista, la ropa que lleva en el anuncio es con la que fue ese día a clase.

La anécdota (nada graciosa) que cuenta Ellen Feiss en el anuncio es totalmente real. Se encontraba realizado un trabajo escolar sobre la implantación de barrios chinos (Chinatowns) en EEUU, cuando el PC de su padre comenzó a pitar (el célebre «beep, beep, beep») y todo se fue al carajo. Según ella, perdió tres páginas de su estupendo trabajo.

El caso es que Feiss se convirtió en un fenómeno de masas. Apareció en vallas publicitarias y en publicaciones destacadas, se crearon clubes de fans, tazas y camisetas con su cara, fue invitada a eventos y a programas de televisión de máxima audiencia y se diseñaron fondos de pantalla, iconos y demás parafernalia sobre ella. Internet se llenó de vídeos a favor y en contra de la muchacha, de textos que declaraban su amor por ella y de otros que la calumniaban y la ponían de yonqui para arriba, de parodias con mejor o peor gusto, de apariciones virtuales en series de animación e, incluso, en Holanda hubo un concurso de imitadores.

Posteriormente protagonizó un segundo anuncio (promocionando el Powerbook G4, de Apple también) que nunca se emitió en televisión y que sólo vio la luz en Internet en el año 2005. Este vídeo tampoco dejó a nadie indiferente por el tono cuasi orgásmico con el que pronuncia la última frase «I love my G4». Más madera para los internautas, que la pusieron de ninfómana calentorra hasta hartarse y crearon vídeos alternativos de cachondeo.

http://www.youtube.com/watch?v=O38-XqqWryo

A día de hoy, la Ellen Feiss de Apple sigue teniendo un club de fans oficial, además de otras webs de seguidores que, poco a poco, van desapareciendo. Asimismo, se ha presentado en varias grandes exposiciones de Apple.

Y decía yo la Ellen Feiss «de Apple» en el párrafo anterior porque la moza ha conseguido hacerse un camino en el mundo de la interpretación, fuera de todo recuerdo a lo que representó en aquella época. Ellen regresó a las primeras planas cuando se anunció que aparecería en un cortometraje francés, llamado Bed & Breakfast (de los directores Martin Beilby y Loïc Moreau), que versa sobre las vicisitudes de una pareja estadounidense que busca a un viejo amigo en Francia. Así fue, el cortometraje se estrenó en el verano de 2006 y en él se puede rememorar el misterio y encanto de su mirada. Todo un lujo para los maqueros freaks. Ella aceptó el papel, incluso sin tener experiencia en el mundo de la interpretación (más allá de los anuncios de marras), pero la crítica aplaudió su papel y la reconoció como una buena actriz en ciernes.

Ellen Feiss en 'Bed & Breakfast'

Ellen Feiss es un buen ejemplo de cómo Internet puede elevar a la fama más efímera al friqui mejor pintado y, al día siguiente, hundir a un personaje con años de culto a sus espaldas. Es el mundo libre y la anarquía digital; es la vida real reflejada en una pantalla de ordenador.

Fulguración solar

El responsable del Departamento de Ciencia, Tecnología y Futuro del diario ABC, José Manuel Nieves, decía en un titular de febrero de 2010 «La NASA anuncia el ciclo de actividad solar más intenso de los últimos 400 años«.  También habló en otro artículo de «La tormenta solar del fin del mundo«. En el último programa de Cuarto Milenio, presentado y dirigido por Iker Jiménez en Cuatro, este hombre fue invitado para comentar su artículo y esclarecer la relación del mismo con las supuestas teorías del «fin del mundo» asociadas a las predicciones ocultas del calendario maya para el año 2012.

Intentaré reproducir aquí, más o menos de forma fiel, sus palabras, porque me pareció una entrevista asaz interesante y cargada de un contenido científico riguroso y, a la vez, asombrosamente angustioso. Al final del post dejo un enlace al programa en cuestión.

2012 es un cúmulo de casualidades. Yo no creo que vaya a ocurrir nada extraordinario, ahora bien, sí es cierto que coincide con una serie de acontecimientos, como las predicciones o profecías mayas, que eran unos muy buenos estudiosos del Sol, de las estrellas y del universo en general. Su forma de considerar el tiempo de manera cíclica ha apuntado a que, justamente, el 21 de diciembre de 2012 se iba a terminar un ciclo. Y eso ha coincidido con que los ciclos que sí conocemos científicamente, los ciclos de actividad solar que se producen cada once años, estén cambiando de período ahora mismo, es decir, acabamos de terminar el ciclo 23 y hemos entrado en el ciclo 24 que, precisamente, entre el año 2011 y el 2012 estará en su punto álgido.

Lo que está claro que está ocurriendo es que estamos entrando en una etapa de mayor actividad solar. Durante los últimos años, el Sol se ha caracterizado por estar quieto, prácticamente no había actividad en él, cosa que sabemos por la ausencia de manchas solares. Esto es normal al final de un ciclo, lo que no es tan normal es que esa falta de actividad dure tanto tiempo (prácticamente la mitad del año 2008 y todo el año 2009). Se han conocido otros períodos (finales de ciclos) iguales, pero duraban meses, no años.

Todo ello, unido a otro tipo de datos del flujo solar, le indica a la NASA que acabamos de entrar en dicho ciclo 24 y que, seguramente, entre los años 2011 y 2012 se produzca la etapa de mayor actividad. Eso quiere decir que aparecerán más manchas solares. Estas manchas está relacionadas con las denominadas fulguraciones solares, técnicamente eyecciones de masa coronal. Una eyección de masa coronal es un fenómeno muy violento que consiste en una expulsión enérgica de una parte de la masa del Sol al espacio, pudiendo alcanzar la materia expulsada millones de toneladas.

Cuando se produce una fulguración solar, el Sol proyecta su masa hacia fuera de él en forma de una emisión masiva de protones y electrones (radiación solar) que, evidentemente, llega hasta la Tierra. El viento solar es algo que conocemos muy bien, porque estamos constantemente bombardeados por partículas que proceden del Sol. Pero cuando se dan estos episodios, la cantidad de materia y de radiación que nos llega es espectacularmente grande.

La Tierra tiene un escudo natural contra este tipo de fenómenos, que es su propio campo magnético (el cinturón de Van Allen). Este escudo magnético absorbe el impacto de la radiación y se deforma con él, esto es, se queda aplastado. Las partículas solares desviadas por el campo magnético se van a los polos y forman el precioso fenómeno de las auroras boreales.

Ha habido eyecciones de masa coronal de muchas y diversas intensidades. La mayor conocida se produjo en el año 1859, y fue tal el impacto de las partículas solares que llegó a deformar el escudo de la Tierra de tal manera que, desde 60.000 kilómetros de altura, que es hasta donde llega el límite del campo magnético, lo aplastó hasta 7.000 kilómetros. Esto significa que el escudo por la parte trasera (el lado contrario al impacto) de la Tierra se estira para, posteriormente mediante una especie de efecto rebote, volver a su sitio y colocarse de nuevo como en un principio.

Las auroras boreales en la violenta tormenta solar de 1859 llegaron hasta los trópicos e, incluso, se vieron en España. Hay artículos de periódicos de la época que recogieron la noticia. Se dijo entonces que el fenómeno llegó a eclipsar el brillo del propio Sol.

Cuando esto sucede, se producen infinidad de descargas eléctricas que llenan toda la atmósfera. En aquel año, la descomunal energía eléctrica con que se sobrecargó la Tierra tuvo otro efecto menos hermoso que el de las auroras boreales. Se frieron, literalmente, las redes eléctricas que había entonces (cuando la electricidad estaba empezando a utilizarse). Además, todas las redes de telégrafos de Europa y de América del Norte se paralizaron por completo durante semanas.

En tiempos como los de hoy, ¿cómo afectaría una tormenta solar de tal magnitud a nuestro mundo? Es la pregunta del millón de dólares. Ese fenómeno, denominado Evento Carrington, que parece que alrededor del año 2012 se podría producir de nuevo, según estudios realizados a tal efecto por la NASA, parece que podría ser un desastre global. Caerían las redes eléctricas de todo el mundo, las redes de teléfono, Internet, los satélites, las redes GPS, la telefonía móvil, etcétera. En fin, el acabose de las telecomunicaciones.

Conforme a esos mismos estudios de la NASA, un Evento Carrington a día de hoy fundiría en los primeros 90 segundos 300 grandes transformadores de la red eléctrica de Estados Unidos. Eso significa dejar, en un minuto y medio, sin luz a 140 millones de personas.

Las redes de GPS ya se han perdido parcialmente en alguna ocasión con fenómenos más livianos que el que sucedió en 1859, pero una fulguración hoy día de aquellas proporciones probablemente las haría caer en su totalidad. Quedarse sin GPS no es ninguna tontería, significa que todas las maniobras aéreas no se podrían realizar, los cálculos de precisión de atraques de grandes barcos no se podrían llevar a cabo, las construcciones masivas de piezas enormes en las que se calculan las posiciones de encaje mediante GPS tampoco, y un larguísimo etcétera. Se bloquearía el mundo.

Además de todo ello, la situación no sería cosa de unas horas, sino que podría alargarse durante meses o durante años (¿años sin electricidad?). El señor José Manuel Nieves termina diciendo que no tenemos ningún tipo de defensa contra eso. Realmente a mí me ha acojonado un poco mucho.

Los mayas anunciaban un fin del mundo que, en realidad, era un fin de un ciclo para comenzar con otro. Un acontecimiento solar como este te hace pensar lo pequeños que somos en el universo y lo grandes que nos creemos. Somos tan frágiles, que un simple estornudo del Sol nos puede mandar a tomar por culo en un abrir y cerrar de ojos. La verdad es que da mucho miedo.

Si alguien desea ver la intervención de este buen hombre, que podía haberse quedado en casa cuando le invitó Iker Jiménez, puede hacerlo desde la página web de Play Cuatro. La entrevista comienza en la hora, minuto y segundo 1:04:20.

Trinity en 'The Matrix Reloaded'

Todos hemos comprobado profusamente cómo se utilizan elementos de la cultura informática en las películas con una suerte bastante desacertada. Incluso cintas que se suponen pertenecientes al género computacional están cargadas de errores informáticos.

Desde ‘Juegos de guerra‘, e incluso bastante antes, los ordenadores han pasado a formar parte de la línea argumental de muchos telefilmes. Y digo desde ‘Juegos de guerra’ porque quizás fuera la primera película dedicada exclusivamente al mundo informático desde la perspectiva del hacking puro, en la que se mostraba una primitiva y rudimentaria Internet.

Esta película, genialmente interpretada por Matthew Broderick, derrochaba imaginación, sin embargo no se le puede achacar un excesivo uso fantasioso de la informática, quizás porque en la época tampoco era posible crear efectos tridimensionales grandiosos y recurrieron a mostrar la austera pantalla negra de la consola y el adolescente introduciendo los comandos a mano. También es cierto que en algunos momentos a los guionistas se les fue la pinza un poco y se generan situaciones digitales bastante inverosímiles (sobre todo para la época); pero es una gran película.

La película ‘La red‘, que tiene como protagonista a Sandra Bullock, es otro de esos títulos de culto en el mundo de hacking, aunque en ella se aprecia más la ignorancia informática de los guionistas y la despreocupación total del director y del productor por fabricar un producto serio más allá de una absurda trama. Direcciones IP que no existen, extraños efectos de interferencias en páginas web que llevan a sitios oficiales, chats imposibles y demás parafernalia son fácilmente reconocibles en ‘La red’. Además, por supuesto, de uno de los principales axiomas del panorama de las películas de tema informático, que dice aquello de que la velocidad de borrado del contenido de un disquete es inversamente proporcional a la tensión emocional de la escena.

Pero existe una película todavía peor, mucho peor. Es la película ‘Hackers  (piratas informáticos)‘. El colmo del despropósito informático, está cargada de interfaces gráficas deslumbrantes, de pantallas de login descomunales (muy típico) y de efectos e instrumentos digitales que se escapan, ya no del mundo de la informática, sino del mundo de la lógica aplastante. Esta película, con  una jovencísima Angelina Jolie en el papel de Kate Libby (aka Acid Burn), tiene de la cultura cyberpunk sólo la estética y poco más.

Angelina Jolie en 'Hackers (piratas informáticos)'

‘Operación Swordfish‘, con John Travolta, es uno de los ejemplos de película en la que la informática sirve únicamente como telón de fondo para el argumento, porque prácticamente nada de lo que dicen tiene sentido. Para muestra un botón. En la siguiente escena (en inglés), archifamosa por lo absurda, Stanley Jobson (Hugh Jackman) tiene que reventar la clave de acceso al Departamento de Defensa de los EEUU en 60 segundos mientras un esbirro del malo le apunta con una pistola a la cabeza y una rubia de traca le practica una felación. Vamos, lo nunca visto.

Es impresionante verle teclear vaya usted a saber qué en el portátil mientras aparecen en pantalla listados larguísimos de términos informáticos sin conexión aparente alguna.

Series televisivas como ‘CSI‘ han metido la gamba también más de una vez. Memorable la imagen siguiente en la que aparece una dirección IP que ríete tú del protocolo IPv6. ¿De dónde se han sacado números tan altos? Por el amor de Dios, ¿qué longitud en bits tienen esas direcciones? ¿Acaso los CSI tienen una red paralela a Internet en la que hay más máquinas conectadas que seres vivos en la galaxia? Y no ha sido la única vez que les pasa.

Error de IP en 'CSI'

En fin, multitud de películas en las que se cometen continuamente errores con el tema informático y que, parece ser, se seguirán cometiendo. Podríamos hablar de la dirección de correo errónea (Max@Job 3:14) en ‘Misión imposible‘, del iPod que lee cientos de códigos en pocos segundos, para escanearlos con un cabezal acoplado en plan MacGyver, en ‘Firewall‘, de obtener una contraseña gracias a la imagen de una cámara de seguridad en ‘Conspiración en la Red‘ o de los cientos de errores típicos que se cometen en todas las películas: programas que amplían una matrícula fotografiada desde tomar por culo hasta que se visualiza perfectamente, monitores con un brillo tal que reflejan su imagen perfectamente en la cara del usuario, listados en pantalla con el soniquete de fondo de una impresora matricial, velocidades de transferencia de datos inverosímiles, etcétera.

Sin embargo, y para nuestro regocijo, existen películas en las que el asunto informático se ha tratado correctamente. Títulos como ‘El ultimátum de Bourne‘, ‘La jungla 4.0‘, ‘El asalto final (Hackers 2: Operación Takedown)‘ o ‘The Matrix Reloaded‘ son buenos ejemplos de películas en los que las escenas con ordenadores son totalmente creíbles, porque aparecen sistemas operativos que existen, software real y comandos reales que, además, se introducen de forma acertada y eficaz para el fin que se desea llevar a cabo.

Y es precisamente en ‘The Matrix Reloaded’ donde los hermanos Wachowski llevaron, a mi entender, el tema hacking hasta su punto más riguroso en la escena en la que Trinity (Carrie-Anne Moss) intenta reventar el acceso al ordenador de la central eléctrica. La foto siguiente muestra a qué escena me refiero.

Hacking en Matrix (clic para ampliar)

En la imagen se puede apreciar perfectamente la pantalla de la consola que Trinity ha manejado una vez realizada toda la secuencia hasta introducir la contraseña. Es un shell no estándar de una consola Unix adaptado al tono verde que tiñe todas las películas de la saga ‘The Matrix’.

Trinity utiliza para reventar la contraseña, en principio, el programa Nmap (en su versión 2.54BETA25, una versión real), que es un software de código abierto que se utiliza en el mundo del hacking y de la seguridad informática para escanear o rastrear puertos en una máquina remota con el objeto de encontrar agujeros de seguridad. Nmap ofrece la posibilidad de encontrar todos los puertos abiertos de una máquina objetivo y poder comprobar así si dicha máquina es vulnerable a un ataque sobre ese puerto.

La línea de comando que emplea ella es la siguiente:

Línea de comando

nmap -v -sS -0 10.2.2.2

El parámetro -v le indica a Nmap que aumente el nivel de mensajes detallados; -sS prepara a la aplicación para un análisis de puertos TCP mediante la técnica SYN; y -O especifica que debe ser activada la detección del sistema operativo que está escuchando en ese puerto.

Un escaneo SYN puede realizarse rápidamente, sondeando miles de puertos por segundo en una red rápida en la que no existan cortafuegos. El sondeo SYN es relativamente sigiloso y poco molesto, ya que no llega a completar las conexiones TCP. A esta técnica se la conoce habitualmente como sondeo medio abierto, porque no se llega a abrir una conexión TCP completa. Se envía un paquete SYN, como si se fuera a abrir una conexión real, y después se espera una respuesta. Si se recibe un paquete SYN/ACK esto indica que el puerto está a la escucha (abierto), mientras que si se recibe un RST (reset) indica que no hay nada escuchando en el puerto. Si no se recibe ninguna respuesta (o si se recibe un error de tipo ICMP no alcanzable) después de realizar algunas retransmisiones, entonces el puerto se marca como filtrado.

Por último, Trinity pasa a Nmap como parámetro final la dirección IP del ataque (10.2.2.2), que es una dirección perfectamente válida de un adaptador de red en un servidor.

Lo siguiente que podemos observar en la imagen son los resultados que ha arrojado Nmap. En este caso sólo ha descubierto un puerto abierto que, casualmente, es el puerto TCP 22, el puerto de SSH (Secure SHell). SSH es el nombre de un protocolo, y del programa que lo implementa, y sirve para acceder a máquinas remotas a través de una red. Permite manejar por completo la computadora mediante un intérprete de comandos y, además, implementa la seguridad que otros protocolos de sus mismas características (como Telnet) no tienen.

Al darse cuenta de que el puerto 22 está abierto en la máquina remota, Trinity, que es una hacker experimentada porque le habrán enchufado en Matrix un programa de esos directo a la mente para aprender a hackear, no se le ocurre otra cosa que utilizar un exploit para reventar la seguridad del equipo y hacerse con su dominio. El exploit utilizado es el SSHv1 CRC32, que existe en la realidad y fue creado por el analista de seguridad Michael Zalewski en el año 2001.

Un exploit es una pieza de software, un fragmento de datos o una secuencia de comandos con el fin de automatizar el aprovechamiento de un error, fallo o vulnerabilidad, a fin de causar un comportamiento no deseado o imprevisto en los programas informáticos, hardware o componentes electrónicos (por lo general computarizados).

A este ataque en concreto contra un servidor SSH se le conoce como SSHNuke. El agujero de seguridad SSHv1 CRC32 es un fallo de desbordamiento de memoria muy real. O quizás mejor lo fue, porque esperemos que los administradores de sistemas no tengan todavía por ahí un servidor SSH con software tan viejo como para contener este error (alguno seguro que hay). Explotado correctamente permite a un atacante remoto modificar su contraseña de root (cuenta de usuario en sistemas Unix que posee todos los derechos) y acceder al sistema vulnerable.

Vemos, por fin, que Trinity ejecuta el exploit, mediante la siguiente instrucción, contra la IP anterior y con el parámetro pertinente para cambiar la contraseña del administrador del sistema:

Línea de comando

sshnuke 10.2.2.2 -rootpw="Z10N0101"

Atención especial al detalle de la contraseña nueva (Z10N0101). Si os dais cuenta está formada por dos partes: Z10N y 0101. Z10N es la forma de escribir Zion (la última ciudad humana real fuera de Matrix) en «leet», que es un tipo de escritura con caracteres alfanuméricos usado por algunas comunidades y usuarios de diferentes medios de Internet, sobre todo los hackers (aunque en «leet» auténtico, la Z debería haber sido sustituida por un 2, dando lugar a 210N). Y el número 101 es una cifra que aparece mucho en toda la saga de ‘The Matrix’.

Una vez que Trinity cambia la contraseña a su antojo, lo que hace es acceder, vía SSH, a la máquina remota con privilegios de root (introduciendo su contraseña recién restaurada).

En fin, muchos directores de películas deberían mirarse en el reflejo de ‘The Matrix’ para, a la hora de introducir temas informáticos en sus obras, recurrir a expertos en la materia y conseguir así un producto digno. Ya sé que, en el fondo, todo esto es de putos friquis como nosotros, y que a la gente que va al cine le gusta ver espectaculares efectos tridimensionales en la pantalla de un ordenador, pero, si no se inventan una forma nueva para conducir un coche, ¿por qué hacerlo para manejar un ordenador?

Seguro que esos directores se gastan más dinero en contratar a expertos pilotos para que el manejo de una jodida avioneta quede realista y luego no invierten un mísero euro en la materia informática. Un error, porque sus películas serán la risión en los foros especializados de Internet, y sus personas de ellos rebajadas a directores de pacotilla. He dicho.

Las máquinas volantes más pesadas que el aire son imposibles.

Lord Kelvin, Presidente de la Royal Society. 1895.

Flujo de un algoritmo

Los algoritmos de ordenación fueron para mí, en un época de mi vida, una especie de obsesión geek que me llevó a investigar, en los albores de Internet, miles de horas delante de la pantalla del ordenador con el único objeto de diseñar algo que fuera más rápido que lo que yo ya conocía. Eran tiempos en los que aún había más información en los libros que en la Red, y en el escritorio se apilaban revistas de informática, libros de programación, disquetes de 5,25″ y decenas de papeles con garabatos esbozados entre apuntes de direcciones web.

El hecho de disponer de una lista (numérica o alfanumérica) desordenada y conseguir ordenarla en un límite de tiempo lógico, ha traído de cabeza a los informáticos de medio mundo desde los tiempos aquellos en los que los primeros profesionales diseñaban aplicaciones bancarias para entidades financieras en lenguaje Cobol. El éxito consistía en lograr obtener un orden rápido y efectivo, ya que no era lo mismo esperar unos segundos para clasificar una matriz de 100 elementos que reordenar las cincuenta mil transacciones que se podían generar en una sucursal bancaria en un día.

El algoritmo de ordenamiento era, pues, muy importante. Pero cada algoritmo que se diseñaba para tal fin no era otra cosa que la genialidad de una mente preclara que, por casualidad o no, discurría un sistema de «cambiar éste de aquí por aquel de allí» para, sucesivamente, recorrer la lista de valores hasta ordenarla completamente.

Las máquinas computadoras, por definición, son tontas de manual. Un ordenador es incapaz de ordenar inteligentemente una lista de valores simplemente contemplándolos, como haría un ser humano. Es por ello que hay que desarrollar algoritmos, que no son ni más ni menos que una sucesión de procesos u operaciones perfectamente documentadas que se ejecutan con el fin de solucionar un problema dado. Posteriormente, estos algoritmos se codifican en un lenguaje de programación para que un ordenador los entienda y los maneje convenientemente.

Entonces, los algoritmos de ordenación son pautas que un software debe seguir para lograr ordenar una lista de elementos rápida y adecuadamente. Existen muchos y de muy variada condición y complejidad. Todos tienen pros y contras y todos contaron en su día (y cuentan hoy) con partidarios y detractores.

A día de hoy cada vez se han hecho menos necesarios estos métodos, ya que los elementos utilizados se almacenan en bases de datos muy avanzadas tecnológicamente y que poseen algoritmos de clasificación y ordenamiento propios. Pero no está mal para cualquier desarrollador conocerlos, porque, de hecho, a la hora de ponerse a programar los necesitaremos en multitud de ocasiones.

Siempre que escribo un post en el que va a haber códigos de ejemplo, nunca sé que lenguaje de programación utilizar; son tantos en la cabeza… Normalmente decido a bulto, para no decantarme por uno solo, así que hoy le ha tocado a Java porque sí, y punto. Se pueden encontrar en Internet multitud de ejemplos en los más variados lenguajes. Es posible que tampoco reseñemos absolutamente todos los algoritmos de ordenación que existen, pero sí vamos a estudiar los más importantes y extendidos.

1. Método de inserción directa (Insertion sort).
Este algoritmo es muy elemental, antiguo y lento, aunque su utilización está justificada en problemas pequeños debido a su bajo consumo de recursos. Este método toma cada elemento del arreglo para ser ordenado y lo compara con los que se encuentran en posiciones anteriores a la de él dentro del arreglo. Si resulta que el elemento con el que se está comparando es mayor que el elemento que ordenar, se recorre hacia la siguiente posición superior. Si por el contrario, resulta que el elemento con el que se está comparando es menor que el elemento que ordenar, se detiene el proceso de comparación, pues se encontró que el elemento ya está ordenado y se coloca en su posición (que es la siguiente a la del último número con el que se comparó).

Código

void Insercion (int[] v) {
   for (int i=1; i<v.length; i++) {
      int aux = v[i];
      int j;
      for (j=i-1; j>=0 && v[j]>aux; j--)
         v[j+1] = v[j];
         v[j+1] = aux;
    }
}

2. Método de selección (Selection sort).
Este método también es muy lento, sin embargo, por su estructura, reduce al mínimo el número de intercambios. Consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición. Luego el segundo más pequeño, y así sucesivamente hasta ordenar todo el arreglo.

Código

void Selecccion (int[] a) {
   for (int i = 0; i < a.length - 1; i++) {
     int min = i;
     for (int j = i + 1; j < a.length; j++) {
        if (a[j] < a[min]) {
           min = j;
        }
     }
     if (i != min) {
        int aux= a[i];
        a[i] = a[min];
        a[min] = aux;
     }
   }
}

3. Método de la burbuja (Bubble sort).
Este archiconocido método es muy parecido al de inserción directa pero mucho más rápido. Fue muy popular cuando apareció porque sustituía a los anteriores bajando drásticamente la velocidad de ordenación. Se recorre el arreglo intercambiando los elementos adyacentes que estén desordenados. Se recorre el arreglo tantas veces hasta que ya no haya cambios. Prácticamente lo que hace es tomar el elemento mayor y lo va corriendo de posición en posición hasta ponerlo en su lugar.

Código

void Burbuja (int[] n) {
   int temp;
   int t = n.length;
   for (int i = 1; i < t; i++) {
      for (int k = t-1; k >= i; k--) {
         if(n[k] < n[k-1]){
            temp = n[k];
            n[k] = n[k-1];
            n[k-1]=  temp;
         }
      }
   }
}

4. Método de Shell (Shell sort).
El método de ordenación Shell, así llamado en honor a su inventor Donald Shell, es considerado un algoritmo avanzado cuya velocidad es notablemente mayor con respecto a los anteriores. Este método utiliza una segmentación entre los datos; funciona comparando elementos que están distantes. La distancia entre comparaciones decrece conforme el algoritmo se ejecuta hasta la última fase, en la cual se comparan los elementos adyacentes, por esta razón se le llama también ordenación por disminución de incrementos.

Código

void Shell (int[] a) {
   for ( int increment = a.length / 2;
      increment > 0;
      increment = (increment == 2 ? 1 : (int) Math.round(increment / 2.2))) {
      for (int i = increment; i < a.length; i++) {
         for (int j = i; j >= increment && a[j - increment] > a[j]; j -= increment) {
            int temp = a[j];
            a[j] = a[j - increment];
            a[j - increment] = temp;
         }
      }
   }
}

5. Método de mezcla (Merge sort).
La ordenación por mezcla o combinación de capas se basa en la estrategia de dividir para conquistar (divide y vencerás). Primero divide el arreglo en dos, ordena recursivamente cada una de las partes y luego las mezcla. El procedimiento debe entonces recibir el arreglo y un par de índices que delimitan los bordes de la ordenación.

Código

public class Mezcla {
   private int A[];
   public int[] Ordenar (int[] L) {
      int n = L.length;
      if (n > 1){ int m = (int) (Math.ceil(n/2.0));
         int [] L1 = new int[m];
         int [] L2 = new int[n-m];
         for (int i = 0; i < m; i++) {
           L1[i] = L[i];
         }
         for (int i = m; i < n; i++) {
            L2[i-m] = L[i];
         }
         L = Mezcla(Ordenar(L1), Ordenar(L2));
      }
      return L;
   }

   public int[] Eliminar (int [] l) {
      int [] L = new int[l.length-1];
      for(int i = 1; i < l.length; i++){
         L[i-1] = l[i];
      }
      return L;
   }

   public int[] Mezcla(int[] L1, int[] L2) {
      int[] L = new int[L1.length+L2.length];
      int i = 0;
      while ((L1.length != 0) && (L2.length != 0)) {
         if (L1[0] < L2[0]) {
            L[i++] = L1[0];
            L1 = eliminar(L1);
            if (L1.length == 0){ while (L2.length != 0) {
               L[i++] = L2[0];
               L2 = Eliminar(L2);
            }
         }
      }
      else {
         L[i++] = L2[0];
         L2 = Eliminar(L2);
         if (L2.length == 0) {
            while (L1.length != 0) {
               L[i++] = L1[0];
               L1 = eliminar(L1);
            }
         }
      }
   }
   return L;

   void GenerarNumeros() {
      Random ran = new Random();
      int x;
      for(int i = 0; i < A.length; i++) {
         x = (int)(ran.nextDouble()*10000);
         A[i] = x;
      }
   }

   void imprimir() {
      for(int i = 0; i < A.length; i++) {
         System.out.println(A[i]);
      }
   }

   int[] getA(){
      return A;
   }

   void setA(int []A){
      this.A = A;
   }
}

6. Método de montículos (Heap sort).
Este algoritmo consiste en almacenar todos los elementos del vector que se desea ordenar en un montículo (heap), para luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos por la cual la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.

Código

import java.util.Arrays;
public class Heap {
   void main(String[] args) {
      int[] arry_int={49,38,65,97,76,13,27,55};
      Heap OrdenaHeap=new OrdenaHeap();
      hsort.OrdenaHeap(arry_int);
   }

   void AjustaHeap(int[] arr, int s,int m) {
      int temp=arr[s];
      for(int j=2*s+1;j<m;j=j*2+1) {
         if(j+1<m && arr[j]>arr[j+1]) ++j;
            if(temp<arr[j])break;
               arr[s]=arr[j];
               s=j;
               arr[s]=temp;
            }
         }

   void OrdenaHeap (int[] arr) {
      for(int i=(arr.length/2-1);i>=0;--i) {
         AjustaHeap(arr,i,arr.length);
      }
      for(int j=arr.length-1;j>0;--j) {
         System.out.println("Elemento superior del montículo arrr[0]="+arr[0]);
         System.out.println("arr["+j+"]="+arr[j]);
         System.out.println("se cambia con"+j+"element");
         int temp=arr[0];
         arr[0]=arr[j];
         arr[j]=temp;
         AjustaHeap(arr,0,j);
         System.out.println(Arrays.toString(arr));
      }
   }
}

7. Método de ordenamiento rápido (Quick sort).
Consiste en elegir un elemento de la lista para ordenar, al que llamaremos pivote. Resituamos los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada. La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote y otra por los elementos a su derecha. Se repite este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado el procedimiento, todos los elementos estarán ordenados.

Código

void Rapido (int[] vector, int primero, int ultimo) {
   int i=primero, j=ultimo;
   int pivote=(vector[primero]+vector[ultimo])/2;
   int auxiliar;
   do {
      while(vector[i]<pivote) i++;   
      while(vector[j]>pivote) j--;

      if (i<=j) {
         auxiliar=vector[j];
         vector[j]=vector[i];
         vector[i]=auxiliar;
         i++;
         j--;
      }
   }
   while (i<=j);

   if(primero<j) ordenarQuicksort(vector,primero, j);
   if(ultimo>i) ordenarQuicksort(vector,i, ultimo);
}

8. Método de ordenamiento Radix (Radix sort).
Es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. La mayor parte de los ordenadores digitales simbolizan internamente todos sus datos como representaciones electrónicas de números binarios, por lo que procesar los dígitos de las representaciones de enteros por representaciones de grupos de dígitos binarios es lo más conveniente.

Código

public class Radix {
   void Radix (int[] arr) {
      if(arr.length == 0)
      return;
      int[][] np = new int[arr.length][2];
      int[] q = new int[0x100];
      int i,j,k,l,f = 0;
      for(k=0;k<4;k++) {
         for(i=0;i<(np.length-1);i++)
         np[i][1] = i+1;
         np[i][1] = -1;
         for(i=0;i<q.length;i++)
         q[i] = -1;
         for(f=i=0;i<arr.length;i++) {
            j = ((0xFF<<(k<<3))&arr[i])>>(k<<3);
            if(q[j] == -1)
            l = q[j] = f;
         else {
            l = q[j];
            while(np[l][1] != -1)
            l = np[l][1];
            np[l][1] = f;
            l = np[l][1];
         }
         f = np[f][1];
         np[l][0] = arr[i];
         np[l][1] = -1;
      }
      for(l=q[i=j=0];i<0x100;i++)
      for(l=q[i];l!=-1;l=np[l][1])
      arr[j++] = np[l][0];
   }

   void main(String[] args) {
      int i;
      int[] arr = new int[15];
      System.out.print("original: ");
      for(i=0;i<arr.length;i++) {
         arr[i] = (int)(Math.random() * 1024);
         System.out.print(arr[i] + " ");
      }

      Radix (arr);
      System.out.print("\nordenados: ");
      for(i=0;i<arr.length;i++)
      System.out.print(arr[i] + " ");
      System.out.println("\nHecho.");
   }
}