Programación del Sinclair QL (V): Algoritmos de ordenación, clasifición y análisis

Índice de entradas sobre programación del Sinclair QL

---

Consideraciones sobre los algoritmos de ordenación

Los algoritmos de ordenación son vitales en informática, no solo para poder presentar los datos ordenados sino para poder optimizar las búsquedas en ellos, como demuestra que el volumen 3 de la serie de 7 de "El arte de programar ordenadores" de Donald Knuth se dedique a "Ordenación y búsqueda". Se considera que el primer algoritmo de ordenación fue desarrollado en 1951 por Betty Holberton, una de las 6 programadoras del ENIAC.

Los primeros ordenadores disponían de muy pocos recursos, por lo que los algoritmos iterativos que no requieren recursos podían usarse, pero si los datos eran numerosos había que recurrir a memoria externa como las cintas magnéticas y en esos casos se usaban la clasificación por mezcla de datos que eran mas efectivas. Cuando la potencia de calculo, la cantidad de memoria y los recursos externos como los discos duros fueron habituales, se crearon los algoritmos recursivos. Aparte de estos hay un cuarto grupo que no son estrictamente de ordenación, mas bien hacen lo contrario y en lugar de ordenar desordenan, que se emplean para estudiar los otros algoritmos.

Para elegir un algoritmo de ordenación hay que evaluar los varios puntos del algoritmo, que son los que utilizan más recursos del ordenador:

• Comparaciones: Para poder ordenar hay que comparar valores, el tiempo empleado en una comparación es proporcional a tamaño del dato, comparar enteros es rápido, comparar cadenas es mas lento. Evidentemente contra menos comparaciones mas rápido, y siempre el que menos necesite será de los más rápidos.
• Intercambios: Para ordenar hay que cambiar el orden de los registros, este tiempo puede ser proporcional al tamaño del dato si se mueve físicamente, o ser lineal si se cambian punteros nada mas. Los algoritmos iterativos mueven muchos datos intercambiándolos en memoria, los recursivos mueven una cantidad pequeña de datos también intercambiándolos en memoria, mientras que los de mezcla los mueven menos pero lo hacen a otras zonas de memoria ocupando mucha mas.
• Memoria auxiliar: Los algoritmos iterativos necesitan muy poco memoria auxiliar para su proceso, los recursivos requieren una cantidad proporcional a los datos que van a manejar, mientras que los de mezcla requieren una cantidad de memoria igual o mayor a la que ocupan los datos.
• Ubicación: Otro aspecto importante es donde de encuentran los datos, si estos están en memoria o en una unidad externa como un fichero en disco, los tiempos de acceso son mucho mas elevados, por lo que minimizando la cantidad de accesos se pueden lograr aumentos importantes de velocidad.

Clasificación según su estructura y análisis general

Como ingeniero informático no puedo dejar de mencionar los ordenes de tiempo y ocupación de memoria de los algoritmos, pero no voy a entrar mucho más, el análisis de algoritmos es un tema muy bonito y complejo por lo que si alguno lo desea puedo discutirlo en otras entradas.

• Algoritmos por intercambio: Se basan en ir intercambiando los elementos de la lista unos con otros ubicándolos o al menos acercándolos a su lugar correcto. Hay dos variantes generales:
  • Algoritmos por intercambio iterativos Son los que menos recursos de espacio necesitan, normalmente solo espacio para guardar uno de los datos a clasificar temporalmente, a cambio requieren mas pasadas entre los datos para ordenarlos. Son mas lentos, pero muy sencillos de programar, por lo que para cantidades pequeñas de datos son los preferidos, el mas conocido es el de Burbuja, que son 4 líneas de programa, en general es también el más lento pero si en un PC moderno ordenar por burbuja 100 datos cuesta menos de un segundo, ¿para que emplear tiempo en hacer otros algoritmos mas complejos? En general tardan un tiempo proporcional al cuadrado del número de registros a ordenar por tanto Velocidad Θ(n²), y requieren solo de un solo dato en memoria por tanto Ocupación Θ(1), por lo que en caso de poca memoria son los mas recomendables, por ejemplo si queremos ordenar 1000 bytes en una máquina con 1024 posiciones de memoria, con esos 24 bytes podemos programar uno de estos algoritmos.
  • Algoritmos por intercambio recursivos o por partición: Consiguen mucha mejor velocidad ya que ubican mas elementos en su lugar o muy cerca a la primera minimizando los intercambios. Van dividiendo la lista en sublistas a partir de un pivote, y las ordenan de forma que todos los elementos de la sublista anterior al pivote sean menores que él y los posteriores todos mayores, pasando luego a realizar el mismo proceso para cada una de las sublistas que se generan. Requieren mas memoria para la recursividad, pero reducen drásticamente el número de intercambios sobre los recursivos. El famoso QuickSort es el considerado mas rápido de los algoritmos de ordenación en casi todos los casos. Su tiempo en general es del orden de Velocidad Θ(n log n), igual que para los de mezcla, pero al ser recursivo Ocupación Θ(log n). Si dispones de memoria suficiente y de un lenguaje recursivo no dudes en usarlo, es sencillo de programar y el mas rápido casi siempre.
• Algoritmos por inserción: Variante de los de intercambio que buscan el lugar adecuado para un elemento y lo ubican en su lugar, desplazando el resto de elementos y minimizando así el número de intercambios. El mas conocido es el de Ordenación por Inserción. También los hay iterativos y recursivos, y su tiempo y ocupación en general es similar a los de intercambio, iterativos Velocidad Θ(n²) y recursivos Velocidad Θ(n log n), aunque al reducir el número de intercambios siempre son un poco mas rápidos. La ocupación en memoria es también similar, los iterativos Ocupación Θ(1) y los recursivos Ocupación Θ(log n).
• Algoritmos por selección: Estos algoritmos funcionan en dos pasos, primero utilizan estructuras auxiliares para clasificar los datos (usualmente creando un árbol), y luego lo recorren montando la lista ordenada. El mas usado es el de Ordenación por Montones (un montón es una forma de arbol binario que usa una lista) Al recorrer la lista una sola vez son rápidos y su velocidad es Velocidad Θ(n log n), pero requieren montar una estructura auxiliar por lo que necesitan tanta memoria como datos a ordena, y por tanto Ocupación Θ(n)
• Algoritmos de mezcla: Son los preferidos para ordenar cuando hay ubicaciones suficientes para ello, y siempre que se realiza en medios de almacenamiento auxiliares y no en memoria. Son mas rápidos pero requieren en general mucho espacio, habitualmente el mismo que ocupan los datos a ordenar si se realizan en memoria, pero se reduce mucho si es en disco. El mas popular entre estos es Merge Sort. Su tiempo varía mucho pero suelen estar en el orden de Velocidad Θ(n log n), y ocupan normalmente lo mismo que los datos a clasificar, por tanto Ocupación Θ(n) trabajando en memoria, pero pueden trabajar muy bien con memoria externa y en este caso Ocupación Θ(1). Apoyados en un medio de almacenamiento masivo son los mejores si estos ya están en memoria externa, así podemos ordenar en poco tiempo una gran cantidad de datos que no quepan en memoria.
• Algoritmos de distribución: Requieren un conocimiento previo de las claves a ordenar, ya que los van clasificando en grupos según un criterio, de forma similar a como se reparte el correo clasificándolo por códigos postales, luego por calles, por números de calle y finalmente por viviendas. El mas popular entre estos es el de Ordenación por Casilleros. Su tiempo es bueno ya que suelen ser Velocidad Θ(nk) , pero ocupan normalmente más que los datos a clasificar, por tanto Ocupación Θ(nk), con una k pequeña que puede llegar a ser 1 en algunos casos, pero con la limitación de ser muy dependientes del conocimiento de los datos a ordenar.
• Algoritmos concurrentes: En este grupo se incluyen algoritmos que se han diseñado específicamente para máquinas con varios procesadores (o varios núcleos) que trabajan a la vez de manera coordinada ordenando los datos. El mas usado es el Cube para ordenar los famosos "cubos" de análisis de datos, realmente arreglos multidimensionales.
• Algoritmos Híbridos: Es usual emplear varios algoritmos a la vez, por ejemplo Quicksort trabaja bien en listas grandes, pero mal cuando son ya pequeñas, por lo que se suele llamar a otro cuando las sublistas tienen ya pocos elementos. Este grupo de algoritmos hacen lo mismo, emplean dos métodos de ordenación complementarios para alcanzar el objetivo.
• Otros algoritmos: En este grupo se incluyen algoritmos especializados en un tipo de datos concreto, como grafos o qbits, o algoritmos muy imaginativos que son solo adecuados para el análisis de algoritmos ya que no son nada eficientes.
• Algoritmos de desordenación: Estos algoritmos son muy usados para producir resultados aleatorios en juegos. El mas antíguo es el Algoritmo del Sombrero. Estos algoritmos ordenan aleatoriamente los datos y repite el proceso hasta que por casualidad estén ordenados, por tanto no se puede usar para ordenar ya que su tiempo es del orden de los algoritmos intratables, con pocos datos puede ser del orden de Velocidad Θ(n!) aunque lo normal es que no acaben nunca. A cambio es muy usado para simular en un programa el barajar las cartas.

Algoritmos estables e inestables

Un registro puede contener claves primarias y secundarias de ordenación, por ejemplo cuando se ordena por Apellidos y Nombre una lista. Se considera un algoritmo estable cuando ordenan siempre los registros con claves primarias iguales en su orden por las secundarias, y se consideran inestables cuando no consiguen mantener el orden dentro de las secundarias. Esta inestabilidad se puede eliminar si unimos las claves primarias y secundarias en una clave única, al desaparecer las claves secundarias desaparece el problema.

Orden y desorden

Un punto importante es cuan desordenados están los datos inicialmente, esto nos puede ayudar a elegir uno u otro algoritmo, hay alguno especializado en listas casi ordenadas. Una forma de añadir un elemento a una lista es ubicarlo al final y llamar a la ordenación para que lo ponga en su lugar, por eso se distinguen tres casos que son los que usaré en las pruebas:

• Caso medio: Los datos están ordenados aleatoriamente, siendo este es el caso genérico que se usa para probar los algoritmos.
• Caso mejor: Los datos ya están ordenados, en este caso los últimos serán los primeros ya que la lenta Burbuja es el que mas rápido acaba normalmente. La comparación de este tiempo con el anterior nos proporciona una idea de la velocidad cuando los datos están casi ordenados.
• Caso peor: Los datos están en orden inverso, que es una buena prueba en la que los mejores algoritmos deben tardar mas o menos lo mismo que en el caso medio.

Las pruebas de los algoritmos de ordenación en memoria las voy a hacer de la siguiente forma para que sean comparables:

1. Genero un arreglo con el tamaño que se indique, y lo relleno de números enteros aleatorios, que pueden estar repetidos. Será el que use luego con todos los algoritmos y así no hay diferencias de partida.
2. Para cada algoritmo que deseo probar:
1. Caso medio: Copio el arreglo sobre uno temporal, y llamo al algoritmo para ordenar el arreglo temporal de menor a mayor. Cuento la cantidad de comparaciones, la cantidad de intercambios y el tiempo en segundos que tarda en total.
2. Caso mejor: Vuelvo a llamar al algoritmo con el arreglo temporal ya ordenado para que lo intente ordenar de menor a mayor, no debe mover ningún elemento del arreglo. Cuento la cantidad de comparaciones, la cantidad de intercambios y el tiempo en segundos que tarda en total
3. Caso peor: Vuelvo a llamar al algoritmo con el arreglo temporal ya ordenado para que lo intente ordenar de mayor a menor, lo que debe cambiar todos los elementos del arreglo. Cuento la cantidad de comparaciones, la cantidad de intercambios, y el tiempo en segundos que tarda en total.
3. Presento los resultados de todos los algoritmos.

Mas adelante lo volveré a hacer con los algoritmos de ordenación externos, que ordenen los datos almacenados en un fichero guardado en el microdriver, haciendo las modificaciones oportunas en el programa base.

Clasificación según su método de ordenación

Según el método que empleen para ordenar los datos hay una serie de familias de algoritmos. Los hay mas o menos rápidos, pero también se han desarrollado algoritmos impracticables, ya que el tiempo que tardan los hacen no abordables, y solo se han usado para el estudio de los algoritmos. No voy a desarrollar todos en superBASIC solo los mas habituales pues la lista es muy extensa, solo pongo aquí los algoritmos las más conocidos y ya son mas de 50:

Por Intercambio	Estos algoritmos son buenos trabajando sobre datos en memoria, trabajan intercambiando elementos de la lista a ordenar para ir acercándolos a su posición definitiva. Todos son variantes del denostado método de la Burbuja, y en general Inestables. Métodos iterativos Ordenación por Burbuja (Bubble sort) Ordenación por Sacudida o Burbuja Bidireccional (Cocktail shaker sort) Ordenación Par-Impar o de Pares y Nones (Odd–even sort) Ordenación de peine (Comb sort) Inestable Ordenación de vaivén o cremallera (Gnome sort o Stupid sort) Ordenación de Algunos Únicos (Several unique sort). Inestable. Algoritmo ineficiente ya que no mejora apenas la velocidad de la burbuja y por tanto solo es usado en análisis de algoritmos. Métodos recursivos Ordenación Rápida (Quicksort) Inestable Ordenación con Ayudante (Stooge sort o Trippel sort). Inestable e impracticable por su baja velocidad Ordenación Tonta (Sillysort). No mejora más que muy ligeramente la velocidad de la burbuja por lo que es un algoritmo ineficiente, solo usado en análisis de algoritmos.
Por Inserción	Se busca el lugar donde ubicar el elemento y se inserta en el, desplazando el resto de elementos si es necesario. Ordenación por Inserción (Insertion sort) Ordenación Shell (Shellsort) Por el nombre de su creador. Inestable Ordenación por Árbol Binario (Tree sort o Binary Tree sort) Ordenación por Árbol Biselado (Splaysort o Splay Tree sort) Algoritmo de la librería o de huecos (Library sort o Gapped insertion sort) Algoritmo de la Paciencia (Patience sorting), por un juego de cartas del solitario de ese nombre
Por Selección	Estos algoritmos utilizan estructuras auxiliares en memoria para aumentar la velocidad de proceso. Ordenación por montículos (Heapsort). Inestable, se considera poco eficiente por lo que no se recomienda su empleo. Ordenación por selección (Selection sort), inestable Ordenación de Dijkstra (Smoothsort) Por el nombre de su creador, muy bueno para listas casi ordenadas. Inestable. Ordenación por Árbol Cartesiano (Cartesian tree sort) Ordenación por torneo (Tournament sort) Ordenación por Ciclos (Cycle sort) Ordenación por Trozos (Strand sort)
Por Mezcla	Dividen los datos en grupos y van mezclándolos de forma ordenada. Su época dorada vino con las cintas magnéticas, y hoy son buenos para ordenación en disco. Ordenación por Mezcla (Merge sort), con su variante del Algoritmo de McCarthy (McCarthy's Algorithm) Ordenación Oscilante (Oscillating merge sort u Oscillating sort) Ordenación Polifásica (Polyphase merge sort o Polyphase sort), y su variante Ordenación por Cascada (Cascade merge sort o Cascade sort)
Por Distribución	Basados en la distribución de los elementos en varios casilleros, de forma similar a como se reparte el correo agrupándolo por códigos postales. Se diferencian principalmente en como se montan los casilleros. Algoritmos de distribución usables Ordenación por Casilleros o por Cajones (Bucket sort o Bin sort), con sus variantes del Algoritmo del Cartero (Postman sort), Ordenación por Huecos de Casillero (Pigeonhole sort), y Ordenación de las Barras o de la Bandera (American flag sort) Ordenación por Raíz o por Base (Radix sort), con variantes de Dígito Mas Significativo (MSD) y Dígito Menos Significativo (LSD) Ordenación por Ráfaga (Burstsort) Ordenación por Particiones (Proxmap sort) Ordenación por Destello (Flashsort) Ordenación por Contero o por Cuentas (Counting sort) Usa una técnica original Algoritmos impracticables Ordenación por Ábaco, por cuentas o por gravedad (Bead sort)
Algoritmos Concurrentes	Diseñados para el procesamiento en paralelo de los datos por varios procesadores simultáneamente. Algoritmos usables Ordenación de Batcher (Batcher odd–even mergesort). Por el nombre de su creador Ordenación en Parejas (Pairwise sorting network). Versión del Impar-Par para varios procesadors en paralelo. Ordenación del cubo (Cubesort). Bueno para arreglos multidimensionales Ordenación por Muestras (Samplesort) Algoritmos impracticables Ordenación por redes (Sorting network) y su variante Ordenación Bitónica (Bitonic sorter)
Algoritmos Híbridos	Es habitual usar varios algoritmos diferentes para acelerar el proceso, por ejemplo se suele usar mucho Quicksort que es bueno para listas grandes, las va reduciendo de tamaño cada vez hasta que son pequeñas, momento en que se usa otro algoritmo mas rápido con tamaños pequeños. Estos algoritmos hacen algo similar Ordenación por bloques (Block merge sort) Algoritmo de Tim (Timsort). Por el nombre del primero que lo programó Ordenación Introspectiva (Introsort or introspective sort) Ordenación por Propagación (Spreadsort) Ordenación sin Arrastre (UnShuffle Sort)
Otros Algoritmos	Algoritmos especializados Ordenación Topológica o de Grafos (Topological sort, Topological ordering, Topsort o Toposort) Algoritmos impracticables solo usados para análisis de algoritmos Ordenación de Tortitas, de Panqueques o de panecillos (Pancake sorting) Ordenación del Espagueti (Spaghetti sort) Ordenación del Diablo (EvilSort) Algoritmos para ordenadores cuánticos Ordenación Cuántica (Quantum sort)
Algoritmos desordenadores	Estos algoritmos desordenan las listas aleatoriamente. Por intercambio Falsa ordenación u Ordenación tonta (Bogosort, Slowsort, Stupid sort, Monkey sort). Impracticable para ordenar pero se usa para desordenar una lista ordenada Por inserción Algoritmo de Fisher-Yates, Ordenación Aleatoria o Algoritmo del Sombrero (Fisher–Yates shuffle, Random Sort o Hat Sort). Solo sirve para desordenar, por lo que es muy usado para barajar las cartas en los juegos. Existe una variante llamada Algoritmo de Sattollo (Sattolo's algorithm) por el nombre de su creador.