Regístrate | Conectar
El Tamiz Libros Recursos Series Únete 7 Users Online
Skip to content

Historia de un Viejo Informático. El Sort (o el viejo problema de ordenar las cosas).




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.

Clasificando Marisco. Crédito: PescaGalicia

Clasificando Marisco. Crédito: PescaGalicia

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.

Diagrama de un proceso de actualización Padre-Hijo

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).

La Tabuladora original de Herman Hollerith

La Tabuladora original de Herman Hollerith

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).

sort-lista-orig

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:

Lista Ordenada

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 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:

Burbuja. Primera Pasada

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:

Burbuja. Tras cinco pasadas

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(n2)). 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:

Burbuja tras siete pasadas

…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 n2, es decir, crece con el cuadrado del número de elementos de la lista..

C.A.R.Hoare

C.A.R.Hoare

…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:

QuickSort. Primera pasada

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:

QuickSort. Segunda pasada

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)

C

En Haskell (autor: bayareaguy)

haskell

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?).

Clasificadora de tarjetas perforadas IBM 85

Clasificadora de tarjetas perforadas IBM 85

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.

Tabuladora IBM 75 (años 40)

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.

Ejemplo de Ordenamiento Externo

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.


Sobre el autor:

Macluskey ( )

Macluskey es un informático de los tiempos heroicos, pero no ha dejado de trabajar en Informática y disfrutar con ella hasta la fecha. Y lo que el cuerpo aguante. Y además, le gusta la música...
 

{ 27 } Comentarios

  1. Gravatar Kent Mentolado | 23/03/2009 at 08:07 | Permalink

    Excelente artículo sobre los algoritmos de ordenación, para mi una de las creaciones mas ingeniosas del ser humano: se conocen decenas de algoritmos diferentes para ordenar! Incluso se siguen desarrollando nuevos algoritmos (se que se publicó uno en el 2004 o 2005, no tengo ni idea de cual era). Como curiosidad, aquí tenéis una página donde se pueden ver una comparación de muchos algoritmos y una pequeña animación que muestra como trabajan: http://home.westman.wave.ca/~rhenry/sort/

    Y ahora voy a contar mi propia batallita, jejeje:

    Cuando era pequeño, mi padre tenia que ordenas muchas facturas debido a su trabajo. Hablamos de centenas o miles de facturas físicas, el tipico papelito de color impreso y rellenado a mano. Como entretenimiento (yo era así de rarito) le ayudaba a ordenar. Su “algoritmo” consistía en dividirlas por montones según la primera unidad del número (si habia facturas del 0 al 9999, preparaba 10 montones, uno con los numeros 0xxx, otro con 1xxx, 2xxx…). Cuando clasificaba todas, repetia la misma operación para cada montón. Con el tiempo, “desarrollé” mi propio algoritmo que resultó más rápido :) Si tenia que ordenar las facturas del 0 al 9999, yo hacia dos montones, uno con las facturas menores de 5000 y otro con las mayores (y como tenemos dos brazos es realmente rápido). Luego, repetía para cada montón. Creo que sin saberlo utilizaba QuickSort :D .

    De nuevo, enhorabuena por el artículo, sigue así :)

  2. Gravatar qwerty | 23/03/2009 at 09:01 | Permalink

    Para ordenamiento en memoria secundaria a mí lo que me suena de EDA son las mezclas de secuencias. Es decir, creo hay otros algoritmos distintos pero para secuencias. Digo porque me da que el método que comentas es bastante peor. Corrígeme si me equivoco. La verdad es que en el día a día más bien suelo tener que recordar qué TAD usar más que los algoritmos de ordenación en sí. Quiero decir que ya viene todo muy mascado, en Java por ejemplo, la diferencia está en entender la diferencia entre el LinkedList y el ArrayList, elegir el algoritmo de ordenación ya es cosa posterior.

  3. Gravatar Macluskey | 23/03/2009 at 09:43 | Permalink

    @Kent: Pues sí, el quicksort para ordenar facturas… si es que cuando uno tiene una necesidad… el ingenio humano no tiene límites…

    @qwerty (qué nombre más original): Lo que llamas “ordenamiento secundario” es lo que yo llamo el Sort. Ya lo describo brevemente al final del artículo: Se ordena lo que cabe en memoria, y luego se va sacando a diversos ficheros temporales; acabado de leer el fichero a ordenar, se comienza a mezclar coordinadamente los diversos bloques de los ficheros, generando nuevos ficheros con bloques más grandes… haste que el último paso se hace un merge, y ya está. En mis tiempos no se podía ordenar nada en memoria (no cabía casi nada en 32 Kb), así que usábamos el Sort para casi cualquier cosa. Y sí, tienes razón: ahora alguien ha codificado los métodos, y la gente los usa, suponiendo que están bien hechos. Bueno, pues algunos, no. Que lo sepáis.

    Acerca de que hay algoritmos mejores… unos son mejores que otros, sin duda. Pero para ordenar en memoria NADA es mejor que quicksort (salvo casos preparados específicamente para fastidiarle). Ya Hoare lo demostró hace una pila de años.

    Gracias por comentar.

  4. Gravatar ender wiggins | 23/03/2009 at 11:18 | Permalink

    Simplemente genial. Soy informático, tengo callos ya de pegarme con sorts y aun así, el artículo ha sido de una clafridad apabullante. Sí señor.

  5. Gravatar elhumero | 24/03/2009 at 12:05 | Permalink

    me has recordado mis clases de COBOL con el SORT. Que tiempos, el examen era un SORT.

  6. Gravatar M. | 24/03/2009 at 12:58 | Permalink

    Oh venerable maestro gremial, gracias por recordar los viejos y oscuros procedimientos arcanos del Arte.

  7. Gravatar Nacho | 24/03/2009 at 01:56 | Permalink

    Sr. Viejo Informático, leo sus textos asiduamente y pese a no haber estudiado ni dedicarme a la informática, me parecen enormemente interesantes. Pero por favor, se lo ruego, deje de usar expresiones como “amenacé con escribir…”, “sufridos lectores…” y similares. Si le leemos es porque nos gusta y lo disfrutamos. Gracias. Un abrazo. :)

  8. Gravatar Macluskey | 24/03/2009 at 07:41 | Permalink

    @Nacho: Bueno, bueno… tenga Vd. en cuenta, querido Nacho, que los artículos son desmesuradamente largos para lo que se da en la blogocosa, y que hay que sentarse pacientemente a leerlos… y que además, como ya he repetido unas pocas veces, me sigue sorprendiendo el gran interés que está levantando esta serie de historietas de abuelo cebolleta. Pero como me lo pide Vd. con tanto respeto, intentaré a partir de ahora comportarme con más mesura.

    Gracias a todos por vuestro comentarios.

  9. Gravatar Jimmy Jazz | 24/03/2009 at 09:19 | Permalink

    Grande!

  10. Gravatar cruzki | 24/03/2009 at 10:40 | Permalink

    Un par de cosas:

    1. A mis alumnos les he estado torturando con estas cosas en la primera práctica. Pero muy poco la verdad.

    2. Añado otro enlace y me copio el de kent :P

    http://www.sorting-algorithms.com/

    1. Se te ha olvidado comentar que el merge (bien programado) es de orden n log(n) (más o menos igual que el quicksort) y además paralelizable!!!. Lo cual lo hace más didáctico y mucho más útil (a fin de cuentas, puedes saber cuanto tarda y no tiene nunca problemas). El realmente sorprendente es el shell, no se sabe aún su complejidad (se cree que existe alguna secuencia de saltos que sea n log n, aunque la mejor que se ha encontrado creo que es n log^2n) que es terriblemente simple.

    2. Kent, el algoritmo que usaba tu padre es el algoritmo Radix (o de la cubeta)[1] Que se supone que tiene orden n pero es muy tramposo. Si tienes mucho números distintos se convierte en un algoritmo de orden n log n con MUCHA memoria externa a usar (con lo cual es más eficiente usar el que tu propones, porque no necesitas tanto espacio y esta más preparado para los humanos :P )

    [1] http://es.wikipedia.org/wiki/Ordenamiento_Radix

  11. Gravatar Macluskey | 24/03/2009 at 01:25 | Permalink

    Amigos todos: He actualizado el artículo para incluir, al final, un breve ejemplo de Ordenamiento Externo, que parece que no había quedado muy claro.

    Mea culpa

    Espero haberlo mejorado. Gracias por vuestros comentarios y sugerencias.

  12. Gravatar lucas | 24/03/2009 at 02:26 | Permalink

    ¿Y qué puedo decir yo, “Sr. Viejo Informático”?

    ¡Genial explicación!

    Para los no informáticos –o simples aficionados–, tus artículos despiertan gran interés, y aunque sean “desmesuradamente largos” es imposible detener la lectura cuando se ha empezado ¡¡!! (¡Y creo que la escritura también! :) )

    Nos vemos pronto Mac; sigue así. Saludos.

  13. Gravatar Mazinger | 24/03/2009 at 03:35 | Permalink

    …”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…”

    ¿Nos gusta? ¡¡¡Nos encanta!!! No hay nada más hipnótico que un bucle infinito… ¡Diablos! Voy a implementar uno ahora mismo… :-)

  14. Gravatar Macluskey | 24/03/2009 at 03:45 | Permalink

    @Mazinger: No pienses mucho, aquí te dejo uno:

    A: If 1 = 1 go to A:

    ¿A que mola? Sin ‘do while’, ni ‘do until’, ni ná: con un goto, como debe ser!!

    @Lucas: Pues muchas gracias, Rey de la Caverna (de Platón, se entiende). Esa es la idea, que los no informáticos puedan leer los artículos sin fenecer en el intento… Me alegra que me digas que lo voy consiguiendo (con esfuerzo, eso sí, que las neuronas no están ya para muchos trotes…)

  15. Gravatar alfema | 25/03/2009 at 09:18 | Permalink

    Cómo me recuerda esto mis tiempos de programación con QuickBasic 3, creo recordar que alguna vez tuve que ordenar datos, como no eran muchos usé el método de la burbuja, pero como no me convencía y después de ver un ejemplo de ordenación que traía el QuickBasic 4.5 apliqué el QuickSort mucho más rápido.

  16. Gravatar Pablo Antonio | 26/03/2009 at 05:27 | Permalink

    Gracias. Ahora entiendo por qué nadie programa en Cobol :)

  17. Gravatar Fernando | 26/03/2009 at 04:08 | Permalink

    Un compañero me ha pasado el link a tus articulos y lo estoy pasando francamente bien leyendolos, doy fe de lo que comentas dado que yo tambien soy del paleolitico, comence a programar en el 69 y continuo en activo.

    En el año 69 yo utilizaba las clasificadoras de IBM para ordenar aproximadamente 20.000 fichas perforadas, el sort vendria mas tarde, para hacer informes de actividad.

    Sigue con tus articulos.

    Gracias

  18. Gravatar Macluskey | 26/03/2009 at 04:40 | Permalink

    @Fernando: Yo no llegué a usar las clasificadoras, el banco donde yo trabajé creo que nunca tuvo ninguna, pero sí que las veía en escaparates en la misma calle: en la Gran Vía de Madrid, por ejemplo, había un par de ellas (era un reclamo de marketing: “Mirad qué modelnos somos, que tenemos trastos de estos”) (y aún no nos preocupaba el terrorismo, al menos no en las empresas: esto cambió con el atentado de ETA en la Central de Telefónica de la calle Rios Rosas) (y, además, no se llamaba “Gran Vía”, sino “Avenida de José Antonio”).

    Gracias por tu comentario, y nada, nada, a seguir en la brecha mientras el cuerpo aguante.

    Gracias a todos por vuestros comentarios.

  19. Gravatar joel | 29/03/2009 at 02:03 | Permalink

    @Kent. Gracias! ¿te puedes creer que hasta que no has puesto tu ejemplo de las facturas no había conseguido nunca entender verdaderamente el quicksort?

    Casualmente yo también, de forma espontánea, ordeno las facturas por el mismo método, e incluso hago “merges” de dos montones de facturas ordenadas, cuando tengo que insertar nuevas facturas en el montón que ya está ordenado. Ahora podré demostrar a mis compañeros matemáticamente que no hay forma más eficiente de ordenar las cosas (ellos usan el método de la cubeta).

    @Mac, te ha faltado explicar que hay algoritmos de ordenación estables e inestables. Los estables son aquellos que cuando se encuentran elementos que ya están ordenados, los dejan intactos. Es decir, que aunque tengan la misma clave, el orden entre ellos seguirá siendo el mismo.

    Por eso hay que tener mucho cuidado al hacer los merges. En tu ejemplo no se puede fusionar los bloques 1 y 4, luego el 2 y 3, y finalmente fusionarlos todos porque los elementos ordenados del 4 quedarian antes que los de los bloques 2 y 3, y se perdería su orden.

    Desde el anterior artículo, me piqué con el Niklaus Wirth, me he descargado su libro en inglés de Estructuras de Datos y Algoritmos, y me lo estoy remirando/reestudiando. Es que aún tengo la asignatura pendiente y con tus artículos se me ha reavivado el interés por estas cosillas. El tema de los algoritmos de ordenación es uno de ellos y francamente, LO HAS EXPLICADO MUY BIEN. (Ahora estoy con los árboles binarios balanceados :-p )

  20. Gravatar Macluskey | 29/03/2009 at 02:42 | Permalink

    @joel: Como me imagino que supondrás, conozco perfectamente lo que es un algortimo de clasificación estable y uno inestable. Me pensé si decir algo en el artículoo no decirlo… y lo ignoré porque me pareció que lo único que iba a hacer era liar más un asunto ya de por sí bastante liado. No aporta mucho al tema, en mi opinión, porque además siempre se puede añadir a la clave de clasificación original un ordinal con el número de registro original, y ordenar por la clave del registro más este número. Además, en los enlaces a la wikipedia y otros, se cita continuamente la estabilidad o inestabilidad del algoritmo. Por fin, a los que usamos el SORT de IBM, si quieres que el porceso sea estable, se le indica la cláusula EQUALS, y entonces se asegura de la estabilidad de la clasificación.

    Quizá hubiera estado mejor citarlo, al menos, pero bueno, tampoco queda tan mal así.

    Luego, lo que comentas de los merges no lo entiendo muy bien. En realidad, mientras se está haciendo merge de bloques pre-clasificados, el orden en que estos se hagan no es relevante. Puedes mezclar el 1 con el 4, luego el 2 con el 3, y cuando mezcles ambos bloques resultantes, lo que te queda es lo mismo que si procedes como cito en el ejemplo, 1+2, luego 3+4 y luego los dos resultantes. Puedes probarlo si quieres con cuatro bloques de tres o cuatro elementos cada uno, y verás que es así.

    Y Wirth… qué recuerdos. Uno de los gurus fácticos de la informática de toda la vida, con Dijkstra, Knuth, Hoare, Codd y Martin… Ya saldrán los que aún no han salido…

    Gracias por tu comentario.

  21. Gravatar joel | 29/03/2009 at 03:59 | Permalink

    Ah, se me olvidó decir que el quicksort no es estable, por lo que el orden en que se hagan las fusiones tampoco es tan vital.

  22. Gravatar Aracem | 13/04/2009 at 11:31 | Permalink

    Magnífico artículo. Para que se dé cuenta la gente de lo importante (bueno, después de tu artículo ya lo saben :D ) que es la ordenación, en la carrera de ingeniería en informática hay una asignatura casi empleada exclusivamente en algoritmos de ordenación y su rendimiento!!! A parte queda también comentar los algoritmos de búsqueda!! Que también tienen su gracia jejeje.

    A mi de los que también me gustaban mucho era utilizar tablas hash, que ordena muy rápidamente ( básicamente con complejidad N si no me falla la memoria) muy buena para ordenar palabras :D aunque claro, prepárate para usar memoria a cascoporro jajaja. Por ejemplo la utilizan los compiladores para que no repitamos variables y fallitos tontos de esos que solemos cometer.

    En definitia, me ha gustado mucho el artículo!!! A ver si me leo el resto de entradas ^^

  23. Gravatar Sacatraca | 16/04/2009 at 07:22 | Permalink

    Y en un programa COBOL, en lugar de hacer un sort interno, si se graban las transacciones en un archivo intermedio, cuyo/s índices/s coincidan con el criterio de ordenamiento y luego se cierra y se lee por la clave deseada … no se obtiene el mismo resultado?

  24. Gravatar Macluskey | 17/04/2009 at 01:56 | Permalink

    @sacatraca: A ver…

    Técnicamente, sí. Funcionaría. Pero no te lo recomendaría, amigo. Es una técnica terriblemente ineficiente.

    Si no te gusta ordenar en memoria interna, ¿por qué no usar un SORT? Sí, una cláusula SORT FICHERO ON ASCENDING KEY tal y tal, USING entrada GIVING salida, por ejemplo.

    Esta cláusula invoca al Sort externo, que siempre será mejor que usar un indexado para eso. Pero me gusta… es lo que yo llamo pensamiento transversal. En este caso no sería una buena solución, pero… pensando así es como los genios encuentran soluciones donde los normalitos no las vemos… Enhorabuena, sigue así!! :D

  25. Gravatar Pentaconto | 25/08/2009 at 12:04 | Permalink

    Hola Macluskey:

    He copiado todos los artículos publicados en esta serie (dí con ella en junio, supongo que buscando por Internet alguna otra cosa), y los guardo como historia de la Informática de los años 70-80′s principalmente, muy diferente a lo que conocemos los usuarios de ordenadores personales (PC’s) y que no somos informáticos.

    En este artículo concreto haces referencia a dos programas para jugar con ordenación de listas, LLAMAQST.exe y LLAMAQS2.exe , que los he descargado, pero al querer utilizarlos para ver qué hacen, me da un error de que falta la librería mfrts32.dll . He mirado por Internet para ver dónde la puedo obtener, pero aunque hay varias entradas que hablan o citan esta librería, no encuentro ninguna donde haya alguna opción de descarga de dicha libería.

    ¿Alguna pista de dónde localizarla?

    Un saludo desde Barcelona.

  26. Gravatar Venger | 19/01/2012 at 04:42 | Permalink

    Qué chulo! Me ha encantado. Aunque un poco lioso para los profanos. Si yo ya sabía que la informática era apasionante…

  27. Gravatar Manolo | 29/12/2016 at 04:49 | Permalink

    El sort de la burbuja en visual: https://www.youtube.com/watch?v=lyZQPjUT5B4

{ 1 } Trackback

  1. Gravatar meneame.net | 23/03/2009 at 07:56 | Permalink

    Historia de un Viejo Informático. El Sort (o el viejo problema de ordenar las cosas)…

    Nueva entrega de la magnifia serie del Viejo Informatico. En esta repasa el Sort. Mas técnico que otras veces, pero muy bien descrito. Para todos los que querais saber la historia del sort, imperdible….

Escribe un comentario

Tu dirección de correo no es mostrada. Los campos requeridos están marcados *

Al escribir un comentario aquí nos otorgas el permiso irrevocable de reproducir tus palabras y tu nombre/sitio web como atribución.