El Cedazo

En la entrada anterior, os prometí (o amenacé, según se mire) contaros qué es y para qué sirve el “Sort”, es decir, el algoritmo de ordenación. Si eres informático, o estás en ello, es muy posible que lo que viene a continuación te aburra, aunque quizá encuentres algo nuevo, quién sabe, porque voy a hacer un poquitín de historia… Y si no eres informático, quizá te ayude a entender en alguna medida los mecanismos mentales que nos gastamos para enfrentarnos a uno de los problemas más incordiantes de la profesión: la gran cantidad de tiempo que se “pierde” (que los ordenadores “pierden”, en realidad) ordenando las cosas… Espero vuestro veredicto.

Por cierto, va habiendo ya unas pocas entradas en la serie; si alguno quiere leer algún otro capítulo de la historieta, ésta es la dirección donde podéis acceder directamente a todos ellos.

A finales del Siglo pasado, una prestigiosa Consultora publicó un estudio que había realizado para averiguar en qué se consumía la CPU de los ordenadores de las empresas. Sospecho que sobre todo, basó su estudio en clientes con mainframes de IBM, aunque sólo sea por lo sencillo que es en estos sistemas conocer con exactitud, gracias al RMF, lo que consume cualquier programa a lo largo del tiempo.

A pocos entendidos sorprendió que el programa que más recursos consumiera fuera el Sort (es decir, el programa standard para ordenar los registros de un fichero, Base de Datos, etc), pero lo chocante fue hasta qué punto lo era: alrededor del 60% de todos los recursos de los ordenadores centrales de las compañías se destinaban a ordenar las cosas (hablo de memoria, porque no he conseguido encontrar el documento ni vivo ni muerto, ni en papel ni en la red).

No debería, en realidad, resultarnos nada sorprendente: lo que los anglosajones llaman “Computer” (artefacto para hacer cálculos), para franceses y españoles es un “Ordenador” (cacharro para ordenar cosas).

Por cierto, el término computer lo aplicaban los anglosajones para designar a las personas que “computaban” una serie de cálculos con una calculadora (calculator). A partir de principios de los cincuenta del siglo pasado, los modernos sistemas fueron reemplazando paulatinamente a los computers humanos, que no sólo se quedaron sin trabajo, sino que también les canibalizaron el nombre…

En fin, el Sort es el programa para ordenar ficheros en todo Sistema Operativo que se precie. Y, que yo sepa, en todos ellos se llama igual: SORT. Desde el B1 del NCR Century 200, hasta el MS/DOS, pasando por el MVS, etc.

Toma un fichero (o varios) de entrada, lo clasifica por las claves que se le indican (o por todo el contenido del registro, si no se especifica nada), de forma ascendente o descendente… Y además, en algunos Sistemas como MVS, el propio programa sirve para hacer tratamientos a los ficheros: Unificar ficheros, Dividirlo en varios, Extraer registros… un programa muy completo, como veis. Y que se usa muchísimo.

Una precisión: los informáticos vejestorios (al menos este informático vejestorio) no decimos mucho “ordenar”, sino más bien “clasificar”. Ya, ya sé que clasificar es distinto de ordenar, y que si traducimos literalmente “Algoritmo de Clasificación” al inglés, nos sale “Clustering Algorithm” (muy usados actualmente para realizar estudios de “Data Mining”), y no “Sorting Algorithm”. Lo que no se debe decir nunca, nunca es “sortear“. Os puede parecer raro, pero yo lo he escuchado muchas veces: “Hay que sortear este fichero”, como si hubiera que rifarlo o jugárselo a la carta más alta… Claro que también decimos mucho que “displayamos” un mensaje, “seteamos” una variable, o “deleteamos” un fichero…

Así que, como la costumbre es la costumbre, a partir de ahora, para no repetirme mucho, diré a veces clasificar, y a veces ordenar. Avisados estáis.

En la vida real se clasifican cosas continuamente, bien para ordenarlas de cara a su almacenamiento, bien para separarlos por tamaños, tipos u otra característica.

Pues igual cuando usamos un ordenador, continuamente estamos clasificando cosas, o el Sistema Operativo lo hace por nosotros, incluso cuando no nos damos cuenta. Cada vez que, en el Explorador de Ficheros de vuestro Sistema Operativo favorito, clicáis en las cabeceras para ver los ficheros ordenadados por fecha, o por nombre o lo que sea, el Sistema invoca internamente al Sort.

Además, todas las Bases de Datos, para poder acceder rápidamente a la información solicitada, requieren tener la información previamente ordenada (o, al menos, tener ordenados los índices de acceso a la información, pero ésa es otra historia y será contada en otro momento).

Cada vez que se requiere recuperar información de una Base de Datos o un fichero para, por ejemplo, presentarla en pantalla, casi siempre se requiere clasificarla (seguramente mediante la conocida cláusula “ORDER BY”), porque los humanos esperamos siempre encontrar la información en cierto orden. Todo fichero que se envíe a algún lugar debe estar ordenado. Los procesos batch que toda empresa realiza (la liquidación de cuentas, la facturación, etc) suelen requerir clasificar una y otra vez los ficheros intermedios. El Sistema Operativo necesita para funcionar mantener ordenada un montón de información…

En definitiva, para que los Sistemas informáticos funcionen como es debido, se requiere que la información esté clasificada… siempre. Y ordenar registros de un fichero o de una Base de Datos es un proceso no muy complicado de entender, pero que consume una enorme cantidad de recursos de máquina.

Siguiendo la filosofía de eltamiz, el mantra que El Gran Jefe Pedro nos repite continuamente: “antes simplista que incomprensible”, intentaré describir el problema, y cómo los informáticos nos hemos ido buscando la vida a lo largo del tiempo para clasificar de forma cada vez más eficiente… a costa de hacer los algoritmos cada vez más complicados, claro.

Cuando no se habían inventado las Bases de Datos, y los ficheros maestros estaban en cinta magnética, para actualizarlos había que leer la última versión (digamos la n) en un armario de cinta, los cambios habidos en el día en otro armario de cinta, y grabar el fichero maestro resultante (la versión n+1) en otro armario más.

El proceso, del que ya hablé en otra entrada,  se conoce como una actualización “padre-hijo” (sí, muy imaginativo no es, pero descriptivo… un rato). Puede haber, además otros ficheros adicionales con otra clase de información, que deben ser leídos también coordinadamente junto con los ficheros principales para realizar correctamente el proceso.

Pues bien, es imperativo para que este proceso pueda funcionar que todos los ficheros que intervienen en el proceso estén clasificados de la misma manera, por ejemplo, por número de cuenta. Si una cuenta no tiene ningún movimiento en el fichero de movimientos, se copia tal cual al nuevo fichero maestro. Pero si tiene movimientos, deben aplicarse a la información anterior (cambios de domicilio, de titulares, etc) y grabar la información resultante en el fichero “hijo” (o no grabar nada, en el caso de que el movimiento sea para “Dar de Baja”). La única forma de saber si una cuenta tiene o no movimientos es ir leyendo en el mismo orden todos los ficheros de forma coordinada, en un proceso que, en sí mismo, se llama, obviamente, “Merge” (Fusión, en español, aunque nadie usa tal nombre).

Como los movimientos se recibían de las oficinas (y se grababan, por lo tanto) en cualquier orden, casi siempre según se iban produciendo durante el día en la oficina, era preciso en primer lugar clasificarlos para poder seguir el proceso para incorporarlos a los Ficheros Maestros.

Y es completamente normal que hubiera que ordenarlos varias veces, por diferentes cosas cada vez, a lo largo del proceso (por ejemplo, para liquidar los movimientos, estos deben estar clasificados por cuenta y fecha de valor; para contabilizarlos, por cuenta contable y fecha de contabilización; para los envíos de las comunicaciones a clientes, por el código postal, etc).

Así que poder clasificar registros fue ya una labor fundamental desde los primeros ordenadores, y lo sigue siendo en la actualidad.

Es más, en los primeros pinitos del cálculo automático (la famosa máquina tabuladora de Hermann Hollerith para realizar el censo de EEUU de 1890), en realidad para lo que servía era para agrupar la información de los ciudadanos, almacenados en tarjetas perforadas, de diferentes formas (por sexo, raza, religión, condado, etc), es decir, ni más ni menos que clasificar la información por diferentes criterios cada vez.

Bueno, y, entonces… ¿cómo nos apañamos los informáticos para clasificar datos?

… Usando Algoritmos de Clasificación, naturalmente.

Aquí viene uno de los invariantes de la profesión: El problema es sencillo, está bien definido, es tan antiguo como la propia existencia de los ordenadores, y por analogía con cualquier otro área de la tecnología, parecería que debería haber consenso práctico sobre cuál es la mejor manera de hacerlo, y ser utilizada por todo el mundo.

Pues no.

No hay un único algoritmo. Hay muchos, cada cual con sus ventajas e inconvenientes, más o menos difíciles de programar, más o menos adecuados a cada tipo de lista a ordenar, y más o menos eficientes. Describiré los más importantes a continuación, pero antes…

>   ¿Cómo ordenamos los humanos una lista de cosas, números, por ejemplo?

Supongamos una lista de cifras que hay que ordenar de forma ascendente, es decir, deseamos colocar los números más bajos a la izquierda y los altos a la derecha (obviamente, la ordenación descendente es idéntica en cuanto al procedimiento, salvo que cambiamos “el mayor” por “el menor”, etc).

Veamos: Se trata de una lista pequeña, de sólo once elementos, así que seguramente la forma más sencilla es elegir de la lista cuál es el número más pequeño, y copiarle en la primera posición a un nuevo “molde” del mismo tamaño. En nuestro ejemplo, tomamos el “01” y lo copiamos el primero. Incluso podemos marcarle, para no equivocarnos y volver a tomarle de nuevo más adelante. Seguimos con el siguiente más pequeño (el 02), luego el siguiente… hasta que terminamos. Lo que queda al final es, obviamente, lo siguiente:

Bien, pues ahora pensemos que esto mismo lo tiene que hacer un ordenador. Queremos escribir un algoritmo (un programa, una lista ordenada de instrucciones, en definitiva) que nos permita ordenar esta lista. En seguida resulta evidente que, para escribir tal obra de arte, hay que tener en cuenta ciertas restricciones que no teníamos en nuestro pequeño ejemplo:

1) Como el número de elementos a ordenar rara vez es fijo (dependerá de cuántas cuentas estamos tratando, que variará de un día a otro, cuántos ficheros, cuántos números, etc), nuestro algoritmo debe servir, sin cambios, para ordenar listas de cualquier tamaño. Desde listas de ningún elemento, hasta listas tan grandes como queramos, pasando por listas de uno, de dos, de once… Particularmente, hay que tener en cuenta que podemos vérnoslas con listas de bastantes millones de elementos, lo que introduce severas restricciones de espacio.

2) Como consecuencia, raras veces es factible pensar en duplicar la lista inicial en otra de igual tamaño: la memoria del ordenador es finita. Por tanto, es una buena idea que nuestro algoritmo trabaje exclusivamente con la propia lista original, intercambiando elementos entre sí sin necesidad de espacio adicional (en realidad sí necesitaremos espacio adicional, para un elemento solamente, que usaremos como memoria temporal para intercambiar dos elementos entre sí… salvo que los intercambiemos usando instrucciones del tipo “XOR“, pero esa es otra historia, y será contada en otro momento).

3) Ya puestos, debemos tener en cuenta que podemos necesitar ordenar los elementos por algo que no sean números: Nombres, Direcciones, Tipos, etc. Y de cualquier longitud (aunque en cada ordenación habrá que avisar a nuestro algoritmo cuál es el tamaño del elemento). Es más, es posible que nuestros elementos contengan varios campos diferentes asociados, y sólo deseemos ordenarlos por uno de ellos. Por ejemplo, es el caso de la ordenación en el Explorador del Sistema: al ordenar la lista de ficheros por fecha, no sólo ordenamos las fechas, sino también toda la información del fichero asociada.

4) Además, podemos encontrarnos con elementos con la misma clave, que deberán quedar todos juntos, y nuestro algoritmo debe estar preparado para ello.

5) Por fin, como podemos necesitar ordenar listas con gran cantidad de elementos, necesitamos que nuestro algoritmo sea eficiente, o sea, que haga su trabajo en la menor cantidad de tiempo posible. Haciéndolo bien, se supone.

.

El algoritmo más sencillo (y uno de los más antiguos) para ordenar una lista de elementos es el “Algoritmo de la Burbuja” (Bubble Sort).

Es muy sencillo e intuitivo: se basa en, comenzando por el primer elemento, ir sistemáticamente comparando cada elemento de la lista con el siguiente. Si están ordenados entre sí, se dejan como están; y si están desordenados, se intercambian entre sí. Después se pasa al siguiente, y se repite lo mismo hasta llegar al final de la lista. O sea, tras la primera pasada, lo que resulta es:

Efectivamente, las dos primeras comparaciones (el 03 con el 07, y el 07 con el 11) han encontrado que el orden relativo de los elementos era correcto, así que no han cambiado nada. Pero en la tercera posición, en cambio, se encontraba el que a la postre ha resultado ser el mayor de todos los elementos (el 11), así que en las comparaciones sucesivas ha sido cambiado una y otra vez con los elementos siguientes, hasta llegar al final de la lista. Primero con el 02, luego el 09, y así hasta el 04 final.

Por tanto, en esta primera pasada, el elemento de clave más alta (el 11) ha quedado correctamente situado en el final de la lista… pero los demás siguen, lamentablemente, desordenados (el nombre “burbuja” viene precisamente porque el elemento de valor mayor se va desplazando por la lista directamente hacia un lado como una burbuja se deslizaría por un tubo lleno de líquido hasta llegar a la superficie). Así que para clasificar los elementos que quedan, no hay más remedio que dar nuevas pasadas de ordenación a la lista. Veamos lo que resulta de las cinco primeras:

En cada pasada sucesiva se ha conseguido ordenar efectivamente un solo elemento, el mayor de los que quedaban desordenados (los sombreados), por lo que es fácil ver que para ordenar completamente la lista necesitaremos dar tantas pasadas como elementos tiene, menos una (la última pasada no hay que darla, pues sólo queda un elemento por ordenar… y ya está, obviamente, ordenado), 10 en nuestro caso. Como en cada pasada examinamos los 11 elementos, este sencillo algoritmo necesita examinar (10 x 11 = 110) elementos para conseguir ordenar la lista (en términos técnicos, su complejidad es del orden de O(n²)). Si hablamos de listas de unas decenas de elementos, no es ningún problema, pero, si necesitamos ordenar centenares de miles de elementos… o millones…

Desde muy temprano, se introdujeron mejoras obvias a la provecta burbuja para hacerla más eficiente. Entre ellos:

- No tiene sentido comparar siempre en cada pasada, a partir de la segunda, todos los elementos, puesto que sabemos positivamente que el último ya está correctamente situado. Así que, en cada pasada, reducimos en uno el número de elementos a revisar. Con esta sencilla medida reducimos a la mitad el número de elementos revisados (y se reduce casi en la misma proporción el tiempo necesario para ejecutar el algoritmo).

- Podemos, en cada pasada, comprobar simplemente si hemos cambiado algún elemento con otro (mediante un indicador, o “switch”, que inicializamos a cero al principio de cada pasada, y que cambiamos a uno cada vez que intercambiamos elementos). Si, después de una pasada completa, el indicador sigue a cero, significa que la tabla ya está clasificada, y podemos ahorrarnos el resto. Volvamos a nuestro ejemplo: tras dos pasadas más (siete en total), tenemos:

…o sea, que ya tenemos la lista ordenada (aunque aún no lo sabemos; hasta que no hagamos la pasada 8, y constatemos que no hemos intercambiado ningún elemento, no estaremos seguros de haber terminado).

Es muy normal en las operaciones reales del mundo real clasificar una lista que ya está clasificada, o casi clasificada, por lo que añadir este indicador es vital en todo buen algoritmo que se precie, siempre que se pueda, pues hay algoritmos donde no es posible.

- En cada pasada, podemos, mientras realizamos el proceso general, averiguar también cuál es el elemento de clave más pequeña (como hemos de revisar todos los elementos, podemos fácilmente anotar dónde se encuentra el más pequeño), y al final de la pasada, intercambiar el primer elemento de todos por ése más pequeño. En la segunda pasada se comenzará el proceso por el segundo elemento, en vez del primero, etc.

Esto reduce el número de pasadas a la mitad (ahora se clasifican dos elementos por pasada), lo que mejora el tiempo ostensiblemente (a costa de mayor complejidad en el algoritmo, claro, que además en su parte interna debe realizar dos comparaciones para cada elemento en vez de una, lo que también consume tiempo).

- Podemos ir cambiando la dirección de la pasada (arriba-abajo y luego abajo-arriba) cada vez que realizamos un cambio, lo que mejora levemente el tiempo requerido para la burbuja.

- También podemos ir comparando no un elemento con el siguiente, sino con uno que esté algo alejado de él (por ejemplo, ir comparando el elemento n con el n+5, en lugar de con el n+1). Esta sencilla modificación a la burbuja, no fue “descubierta” nada menos que hasta 1991, y sorprendió por sus excelentes resultados.

Con este sistema, se intenta eliminar en lo posible las “tortugas”, que son aquellos elementos de clave pequeña (que acabarán por estar al principio de la lista) pero se encuentran inicialmente situados al final. Por el propio funcionamiento de la burbuja, en cada pasada sólo suben una posición hacia arriba, lo que ralentiza mucho la terminación del algoritmo. Si os fijáis nuevamente en nuestra lista de números, veréis cómo el “04” va subiendo lentamente desde el final, pasito a pasito, hasta alcanzar su posición final.

Este algoritmo (Combsort) mueve con rapidez las “tortugas” hacia arriba, por lo que tiene un excelente rendimiento, a cambio de una mayor complejidad de programación, comparado con la burbuja… aunque siempre compensa, desde luego.

Por fin, existen otros algoritmos que hacen más o menos la misma cosa de formas diferentes, y que, según el caso funcionan mejor que la burbuja, como son el Ordenamiento por Inserción, el  Ordenamiento por Selección, etc, pero ninguno de ellos es muy eficiente, pues todos tienen una complejidad del orden de n², es decir, crece con el cuadrado del número de elementos de la lista..

…O sea, mucho. Cuando tratamos con grandes volúmenes de información, casi siempre es inaceptable.

Los informáticos rara vez nos conformamos con lo que tenemos, así que desde el principio nos pusimos a solucionar este problema (se pusieron, en realidad, que uno es viejo, pero no tanto). Y uno de los gurús de los albores de la Informática, C.A.R. Hoare, solucionó el problema nada menos que en 1960. Y digo lo solucionó porque no sólo describió el algoritmo (el famoso Quicksort), sino que, algún tiempo después, demostró matemáticamente que era el más rápido posible para ordenar listas.

El Quicksort se basa en el famoso aforismo de Julio César: “Divide y Vencerás”. Y eso es exactamente lo que hace el algoritmo:

1. Elegimos un elemento (en principio, cualquier valor de la lista) cuyo valor usaremos como pivote. Unas implementaciones toman el primero, otras el último, a mí siempre me ha gustado más elegir el elemento que está en la mitad de la lista; luego veréis por qué.

2. Recorremos la lista entera, con el objetivo de colocar los elementos de clave menor que el pivote a la izquierda, y los mayores, a la derecha. De hecho, en las mejores implementaciones, como la de Sedgewick esta fase suele hacerse recorriendo simultáneamente la lista en las dos direcciones; cada vez que se encuentran un par de elementos descolocados, se intercambian entre sí.

3. Acabado este proceso (ojo, no es exactamente tan sencillo como parece), lo que queda es un conjunto de elementos menores que el pivote, luego el pivote (si hay claves duplicadas, todos los elementos de clave igual a la del pivote), que ya está(n) correctamente colocado(s) en su posición final, y luego otro conjunto de elementos con clave superior al pivote.
Conseguir esto es lo óptimo, pero, dependiendo de la implementación, puede quedar la lista dividida en sólo dos conjuntos: el primero, con los elementos de clave menor o igual que el pivote, y el segundo, con los elementos de clave mayor o igual. Es algo menos eficiente, pero también menos complejo de programar.

4. ¿Y ahora?   Pues ahora hacemos lo que hacemos los informáticos desde el principio de los tiempos siempre que podemos: reutilizamos el código. Es decir, le aplicamos exactamente el mismo proceso descrito antes (de 1 a 3), primero al primer conjunto de elementos (menores que el pivote), y luego al segundo (los mayores que el pivote). Y ya está.

Fácil, ¿no?.

Pues, para variar, no.

Esto de que un algoritmo se llame a sí mismo se llama recursividad, y aunque es una técnica muy potente, siempre nos da un poco de yuyu a los de la profesión, porque hay que controlar muy, muy bien cuándo hay que terminar el proceso, para evitar meter el programa en un hermoso bucle infinito, con lo que eso nos gusta…

Si volvemos a nuestro ejemplo, suponiendo que lo hemos programado todo bien, y tomando como pivote el primer elemento de la lista (para no andar en el ejemplo calculando la posición media), tras los pasos 1 y 2 (selección del pivote y recolocación de elementos), tenemos lo siguiente:

El primer elemento, el elegido como pivote (“03”) ha quedado efectivamente colocado en su lugar definitivo, y ahora tenemos dos conjuntos de elementos, los menores que “03” a su izquierda, y los mayores a su derecha.

Ambos conjuntos están en principio desordenados (el de la izquierda ya está bien, pero no hay forma de que el algoritmo pueda saberlo todavía). Ahora hay “simplemente” que aplicar la misma medicina a los dos conjuntos de elementos: primero al uno y luego al otro. ¿Hasta cuando?

Pues hasta que el subconjunto que haya que clasificar esté necesariamente ordenado… lo que ocurre cuando tiene tamaño cero o uno (es decir, hay uno o ninguno elementos a clasificar). No os extrañe que hable de “cero elementos”, es perfectamente posible: si en el ejemplo hubiésemos tomado como pivote el elemento central (o sea, el que está físicamente en medio de la lista), el valor elegido hubiera sido el “01”… que resulta que es el de clave más pequeña, y por tanto hubiera quedado ubicado en el extremo izquierdo de la lista, por lo que no hubiera tenido ningún elemento a la izquierda, y todos los demás, desordenados, a la derecha.

En definitiva, si el tamaño del subconjunto a ordenar es menor que dos, no ejecutamos esa parte, garantizando que el algoritmo termina. Es más, podemos mejorar significativamente el rendimiento del algoritmo si, cuando el tamaño del subconjunto es exactamente dos, en lugar de volver a llamar recursivamente al algoritmo, nos limitamos a comprobar si están bien (y los dejamos) o mal ordenados (en cuyo caso los intercambiamos), evitando una re-llamada recursiva al algoritmo para ordenar tan sólo dos elementos.

Sigamos con nuestro ejemplo:

El subconjunto “01”,”02”, está ya clasificado (como tiene dos elementos, hemos comprobado si estaban en orden; como lo están, los mantenemos). Tratamos entonces sólo el segundo subconjunto. Elegimos el pivote (el primer elemento, hemos dicho: el “09”, pues), e intercambiamos elementos para mover los menores a la izquierda y los mayores a la derecha. Esto es lo que queda:

El tramo de elementos a la derecha del pivote (“10”, “11”) sólo tiene dos elementos, luego los ordenamos entre sí si no lo estuvieran ya, y nos dedicamos ahora al subconjunto izquierdo (los cinco elementos que siguen sin sombrear). Y así sucesivamente.

Casi se ve a simple vista que es un procedimiento muchísimo más rápido que la burbuja con todas sus variantes… aunque es también bastante más complicado de programar correctamente. En general (salvo casos especialmente preparados para fastidiarle, obligándole a tomar siempre como pivote al peor de los elementos posibles), el número de elementos a revisar, su complejidad, pues, es del orden de n·log n (el logaritmo, en base 2), siendo n el número de elementos de la lista.

Para una lista de cien mil elementos, la burbuja necesitará revisar del orden de diez mil millones de elementos para clasificarla (con las diferentes mejoras, quizá lo reduzcamos a sólo mil ó dos mil millones). Quicksort necesitará revisar del orden de 1,5 a 2 millones de elementos para hacer el mismo trabajo. Bastante menos, y además, la diferencia es mayor cuanto mayor sea el tamaño de la lista.

El punto “débil” de Quicksort es la elección del pivote. Si la elección es sistemáticamente mala (es decir, es de los primeros  o de los últimos de la lista ordenada, pero no alguna vez, sino siempre), su rendimiento puede ser mucho peor de lo esperado. En cambio, si, por algún sortilegio, elegimos siempre como pivote el elemento que ocupará exactamente la posición central de la lista definitiva, su rendimiento será óptimo.

Muchas implementaciones de Quicksort aplican diversas estrategias para optimizar en lo posible esta elección, como tomar el primero, el último y el central, y hallar la media (si son números, claro, porque si son nombres… no sé yo cuál será la media de “Sánchez” y “Pérez”, no sé…¿quizá “Rodríguez”, je, je?).

Otras, directamente se revisan la lista para asegurarse de tomar el mejor valor (el que, al final de la partición, quedará exactamente en el punto medio de la lista)… con un proceso que también es costoso, así que muchas veces no compensa; o bien utilizan una solución más de andar por casa (la que a mí me gusta) que es simplemente tomar como pivote el elemento central de la lista (si tiene, por ejemplo, 100 elementos, el que ocupe la posición 1+100/2 = 50). Esta suposición puramente empírica se basa en que las listas del mundo real no son casi nunca aleatorias, sino que suelen tener algún tipo de ordenación o cuasi-ordenación. Según la Ley de los Grandes Números, es bastante eficiente usar esta estrategia, pues en muchos casos la posición final del pivote elegido no estará muy alejada de su posición inicial. Nada científico, como veis. Lo que sí puedo asegurar es que, en el mundo real, funciona de maravilla.

Quicksort es, efectivamente, un algoritmo relativamente complejo, pero también es uno de los algoritmos más estudiados, trabajados y optimizados por informáticos de todo el mundo, que han conseguido reducir el código necesario hasta extremos… bueno, hasta el extremo.

Tres ejemplos:

En Python (autor: Nathan Gray)

En C (autor: Harry Hardjono)

En Haskell (autor: bayareaguy)

Sí, definitivamente son algoritmos bastante “oscuros“. No me preguntéis si funcionan o no, no tengo ni idea (aunque me da en la nariz que no funcionan del todo: puro instinto informático, desarrollado con los años). Pero ya veis, hay quien es capaz de codificar el algoritmo en sólo tres o cuatro líneas, luego… ¡no será tan difícil!.

Aunque yo, que lo mío es el Assembler y el Cobol (igual no se había notado), necesito bastante más de tres líneas para codificarlo…

A continuación os dejo un pequeño regalo, que quizá alguno de vosotros agradezca (no muchos, seguro): una implementación, muy cercana a la más eficaz, del algoritmo Quicksort… en Cobol, claro. Aseguro que funciona. Palabrita. Siempre, en todos los casos (excepto cuando la lista a ordenar está vacía, porque soy vago y no he puesto el IF correspondiente).

Éste (de nombre QUIKSCBL.txt) es el propio programa que implementa el Quicksort (en un módulo, que es la forma chachi de hacerlo), y este otro, para probarlo, es un posible programa principal (de nombre LLAMAQST.txt), que llama al módulo anterior con una pequeña lista de 600 elementos precargada (aunque en realidad son dos bloques duplicados de 300 elementos cada uno) y después muestra por pantalla la lista clasificada. El resultado de la compilación y linkedit de ambos (para Windows, en principio cualquier Windows, pero… ¡quién sabe!), el ejecutable (LLAMAQST.exe), lo tenéis aquí. Y por fin, aquí tenéis el ejecutable de otra versión del mismo programa (LLAMAQS2.exe) pero esta vez clasificando una cantidad más respetable: 9000 elementos (30 bloques de los mismos 300 elementos; éste último primero muestra la lista, para que se vea que está bastante desclasificada, luego la clasifica, y al final la vuelve a listar, ya clasificada; como son 9000 elementos, tarda un poquito… ¡en listarla!).

Podéis probarlo si gustáis, mejor en una ventana del Sistema (prometo que no tiene ningún virus: ventaja de estar escrito en Cobol)… ¡Vuela!. De hecho no se nota ninguna diferencia apreciable entre clasificar 600 o 9000 elementos; le das a la tecla, y ya está…

Para acabar, si de verdad os interesa y tenéis tiempo, en esta página encontraréis una interesante charla de John Bentley sobre cómo escribir un Quicksort bueno, bonito y barato … y sólo dura una hora (la conferencia, digo).

…Y aquí termina este artículo dedicado a la Ordenación…

…

No, claro que no. Porque estos algoritmos ordenan listas en la memoria del ordenador, que tiene la fea costumbre de ser de limitado tamaño… así que ¿qué ocurre si deseamos clasificar una lista de varios millones de elementos, que, en definitiva, no cabe en la memoria?  (Traducción al lenguaje de los años setenta, con la escasísima memoria de los ordenadores de entonces:  ¿Cómo se clasifican todas las listas, por pequeñas que sean?).

Pues hay que recurrir al Ordenamiento Externo, es decir, usar dispositivos de memoria externa para realizar la clasificación.

Ahora se usa siempre disco magnético para estos menesteres, pero yo he utilizado Sort en Cinta Magnética en mis años mozos (con 32 Kb de memoria, no había mucho espacio para ordenar nada en memoria, como es evidente, y con discos de 4 Mb, en muchos casos no era tampoco factible usarlos).

E incluso antes que eso, se clasificaban los ficheros en tarjeta perforada, mediante unas máquinas especializadas llamadas “Tabuladoras” (Tabulating Machines). La primera fue la que construyó Hollerith para el dichoso censo de 1890; con el paso del tiempo llegaron a una gran perfección.

Tomaban un taco grande (de decenas o centenares de miles de tarjetas), las leían y las iban clasificando en diferentes cajetines por el campo que se definiera.

Cuando acababa el primer paso del proceso, y se tenían todas las tarjetas iniciales separadas en montoncitos en los cajetines, se iba haciendo el mismo trabajo con el contenido de cada uno de los montones, hasta que quedaba clasificado el fichero completo. Vale, tardaba mucho, era bastante manual y propenso a errores, pero mucho menos que hacerlo totalmente a mano.

Atención: Batallita. Pensábais que por una vez os íbais a librar, ¿eh?

Como anécdota, recuerdo que cuando yo era muy, muy joven, es decir, un niño (debía ser a principios de los sesenta, ¿1961, 1963?… por ahí) había un Concurso en la Tele (en directo, claro; TODO era en directo entonces; y no preguntéis en qué Tele; en la Tele y punto) donde cantaban ciertos artistas de la época de los que, obviamente, no me acuerdo… aunque seguro que al menos Raphael y Manolo Escobar pasarían por allí…

Los televidentes (los pocos que había entonces, pues la Tele no comenzó a emitir en España hasta finales de 1956) compraban, creo recordar que en los Estancos, durante la semana siguiente a la emisión del concurso, unas tarjetas preimpresas y sin perforar, donde esos televidentes/concursantes agujereaban de no sé qué forma, seguramente con lápiz (los más avanzados, bolígrafo), cuáles habían sido los cantantes que más les habían gustado, y las enviaban luego a la Tele.

Entonces todas las tarjetas, agujereadas de aquélla manera (o sea, que vaya Vd. a saber lo que de verdad habría allí perforado) se pasaban por una tabuladora de aspecto imponente (o al menos eso nos parecía a los atónitos teleespectadores) durante el programa siguiente, en riguroso directo, claro, y de allí surgía, por arte de tecnológica magia, el taco de las tarjetas que habían acertado quién ganaría, o quién cantó mejor o algo así, y los acertantes se repartían finalmente un premio de algunos miles de pesetillas para todos.

La tabuladora tenía un aspecto similar a ésta de aquí arriba (que es de los años 40, ¿eh?), o al menos así la tengo en mis infantiles recuerdos.

Representó un auténtico empujón hacia la modernidad para nuestro país y para la época: efectivamente fue la primera vez que muchos se enteraron que existían estos artefactos y para qué valían… y el auténtico precursor de los hoy inevitables concursos de envío de SMS’s… ¡SMS’s de cartón y por Correo Certificado, eso sí que es friki!.

(Lo siento, sé que prometí que este post no iba a tener batallitas, pero, ejem, es que no he podido resistirme…)

Volviendo al Sort, para clasificar un fichero mediante Ordenamiento Externo, el sistema utilizado se basa en utilizar toda la memoria interna posible (por escasa que sea ésta), llenarla con la primera parte de la lista original (todo lo que quepa), ordenarla en memoria, y copiarla una vez ordenada a la memoria externa (en diferentes ficheros temporales, alternándolos), e ir realizando esta función hasta terminar la lista. Entonces se comienzan a leer coordinadamente (Merge, ¿recordáis?) los ficheros temporales, por bloques (los mismos que han sido ordenados en memoria), generando nuevos ficheros temporales, que tendrán bloques más grandes… hasta que, en una última pasada, se obtiene el fichero definitivo clasificado.

No deja de ser parecido a lo que hacía la máquina de Hollerith, aunque sin tarjetas. Tardar, tarda más que hacerlo en memoria. Muchísimo más. Pero, cuando no queda más remedio…

Veamos cómo funcionaría un ordenamiento externo con un pequeño ejemplo: Supongamos que queremos ordenar un fichero que tiene, digamos, 550.000 registros, pero en nuestra memoria interna disponible sólo nos caben 100.000… Hay que hacer una Clasificación Externa, pues.

Como necesitamos espacio temporal adicional, supongamos que definimos cuatro ficheros temporales para su uso por el algortimo (cuantos más ficheros definamos, más eficiente será el proceso, como fácilmente podremos ver en unos momentos). Estos ficheros temporales son puramente secuenciales, por lo que podrían estar en disco, en cinta magnética, incluso en tarjeta perforada, si encontramos…

Lo primero que hacemos (FASE 1) es ir leyendo bloques de 100.000 registros (los que nos quepan en la memoria), y una vez allí, clasificarlos por un algortimo rápido (QuickSort o HeapSort suelen ser los preferidos). Una vez ordenados, los escribimos en los ficheros temporales 1 y 2, alternativamente.

En la imagen podemos ver cómo los seis bloques en que se divide el fichero (5 de 100.000 y el último de 50.000 registros), una vez clasificados internamente, van a parar, los bloques 1, 3 y 5, al fichero temporal 1, y los bloques 2, 4, y 6, al temporal 2.

A partir de ahora, ya no usamos ningún algoritmo de clasificación, sino sólo de mezclado: el Merge, del que ya hemos hablado antes. Efectivamente, en FASE 2 leemos coordinadamente los dos primeros bloques (1 y 2), de ambos ficheros, generando un bloque de 200.000 registros clasificado, que escribimos en el fichero temporal 3. Luego hacemos lo mismo con los bloques 3 y 4, grabando ahora en el temporal 4, y luego los 5 y 6, que grabamos en el temporal 3 nuevamente.

En FASE 3, leemos los ficheros temporales recién creados (3 y 4), y reusamos los temporales 1 y 2; ahora hacemos merge sobre bloques de 200.000 registros ya clasificados; primero se mezclan los bloques 1+2 y 3+4, grabando el resultado, ya ordenado, al temporal 1. El bloque 5+6 se graba en el temporal 2, puesto que no quedan bloques en el temporal 4 con los que mezclarse.

Por fin, la FASE 4 vuelve a mezclar los bloques de 400.000 registros de los temporales 1 y 2, generando, en este caso, el fichero final ya clasificado. Si tuviéramos más registros, en FASE 5 los bloques serían ya de 800.000 registros, en FASE 6, de 1.600.000, etc. En definitiva, hemos usado un algoritmo “Mergesort“, que es muy eficiente y, además, paralelizable, aunque tiene una pega: necesita memoria adicional, al menos tanta como la que ocupe la lista original a ordenar (mejor, el triple, no vaya a cascar a mitad del trabajo…). Es decir, Mergesort es el algoritmo de referencia cuando el ordenamiento ha de hacerse en memoria externa.

Como podéis imaginar, este algoritmo básico es susceptible de ser mejorado bastante. Por ejemplo, usando seis ficheros temporales en vez de cuatro, podría hacerse el mismo trabajo en sólo tres Fases, no cuatro. También, en la Fase 3, no sería necesario grabar los bloques 5+6 al temporal 2, sino que la Fase 4 podría mezclar el temporal 1 con el temporal 3, a partir del punto exacto donde se quedó… y otras muchas que se os ocurrirán. Pero vamos a dejarlo aquí, en aras a la (ya inexistente) brevedad del artículo.

Espero haber sido instructivo a la par que ameno.  Eso espero…

En la próxima entrada volveremos a las batallitas, esta vez para recordar cómo comenzaron los cambios en la informática que nos llevaron de cabeza a la que conocemos en el Siglo XXI: La irrupción de los PC’s en la empresa (y algún tiempo después, en nuestras vidas), a mediados de los 80.

Disfrutad de la vida, mientras podáis.