Ordenación de Vectores I

Cualquiera que esté cercano a las ciencias de la computación habrá sufrido en sus primeros estudios la realización de prácticas de Ordenación de Vectores, un tema básico en algoritmos y estructuras de datos.

Esta problemática es de extrema importancia aunque no tenga una visibilidad reconocida, pongamos un ejemplo (no es de ciencia ficción): Cómo ordenaríamos fotones o cómo realizaríamos una simulación basada en partículas, pues tan fácil como usar GPU bucket, Bitonic o cualquier otro algoritmo adaptado a las circunstancias.

Algo a tener en cuenta, algunos de los algoritmos que se han publicado son teóricos y muestran que se comportan mejor que los que están englobados en los de comparación, de casillero o radix, pero a pesar de sus ventajas teóricas, no son una mejora para los rangos típicos y prácticos de ordenación. El mejor algoritmo de clasificación es aquel cuya suma media del número de comparaciones, movimientos e intercambios es mínima.

Este artículo se introduce en los conceptos, estructuras y algoritmos que han intentado obtener el mejor rendimiento en el proceso de ordenación. La ordenación en red y con computación paralela se abordará en artículos posteriores.

Los algoritmos desarrollados, en Ordenación de Vectores II, están orientados a trabajar con números enteros positivos, algunos de estos podrán trabajar con otro tipo de dato realizándoles pequeñas modificaciones. Esto tiene una pequeña explicación: algunos de los algoritmos base contienen errores o los han contenido y puede que algún otro lo contenga, para no arrastrar esos errores cierro el círculo tratando de que lo que se publica esté libre de ellos. Ejemplos de esta situación:

• En 1.971 M. Foley y Antony R. Hoare publican la primera prueba de corrección de un algoritmo de ordenación, la del Quicksort.
• En 2.015 se detecta que Timsort en Android, Java y Python no funciona correctamente.

Por otro lado

• En 1.999  J.C. Filliâtre y N. Magaud garantizan que los algoritmos de Inserción, Montículo y Quicksort trabajan de forma correcta.
• En 2.013  C. Sternagel certifica que Mergesort también es correcto. Recordemos que Mergesort viene del año 1.945.

Esto nos puede dar una idea de la incertidumbre que nos pueden transmitir algunos algoritmos. Quizás debamos construir una entidad de certificación que garantice la idoneidad de los algoritmos de uso público (Programas Marco de la UE) y exigir responsabilidades a los patentados y propietarios de marca.

Tipos.

Los algoritmos de ordenación pueden estar dentro de tres grupos:

1. En función de dónde están los datos.
   • Internos. Los datos caben en la memoria principal y allí se procesan.
   • Externos. Los datos no caben en la memoria principal y residen en un almacenamiento externo. Para esta situación algunos algoritmos que son eficientes en la memoria principal pueden no serlo cuando en el tiempo de ejecución se incorpora el número de operaciones de entrada y salida (E / S). Lo vermos más adelante, pero los mejores algoritmos secuenciales de ordenación operan con O (n log n), en comparación los externos ya solo en la lectura de la entrada tienen O (n). En el supuesto de tener solo un dispositivo externo, cualquier algoritmo requerirá accesos externos de O (n²). Es una problemática de tiempos pasados pero hay que conocerla.
2. En función de la existencia de operaciones de comparación
   • Comparables. Los elementos del vector se comparan entre sí, son la inmensa mayoría de los existentes y en promedio no puede funcionar más rápido que Ω (n lg n). Estos obtienen información sobre el orden relativo de los elementos a través de comparaciones por pares. Su tiempo óptimo de ejecución es O (n log n), sin embargo, este modelo no es el más natural para el estudio de problemas de ordenación, ya que las máquinas actuales permiten muchas operaciones además de la comparación. Usando direccionamiento indirecto es posible ordenar enteros en tiempo lineal a través del algoritmo de Cubetas / Bucket, lo que demuestra que el límite inferior basado en la comparación puede no ser correcto en el contexto de la ordenación de enteros.
   • No comparable. No comparan los elementos del vector entre sí, utilizan caracteres internos para reorganizar los valores en el orden correcto, por ejemplo: Radix.
3. Según el uso de procesadores.
   • Secuenciales. Utiliza 1 solo proceso, ejecutando las instruciones una detrás de otra.
   • En Paralelo. Utiliza un número de máquinas, núcleos o procesos > 1. Las instruciones pueden dividirse o agruparse ejectándose en distintos procesadores o máquinas en el mismo tiempo.

Todos los grupos son combinables.

También podemos clasificalos según su estructura:

• Adaptativa. Eficiente para conjuntos de datos que están parcialmente ordenados, también denominada Smoothness (Suave), este término fue introducido por Edsger W. Dijkstra en 1.981 cuando publicó una variante del algoritmo del Montículo-Heapsort denominada Smoothsort. Una ordenación es suave o está desbastada, cuando su rendimiento mejora de O (n log n) a O (n) si la entrada ya está ordenada en algún grado, a esto se le denomina ordenación adaptativa. El vector ordenado cumple esta definición cuando el tiempo de ejecución T(n) = O(n log n), donde n es el número de valores distintos de los elementos. La ventaja de smoothsort es que se acerca al tiempo O (n), mientras que el promedio es O (n log n) independientemente del estado inicial.

• Complejidad. Referente a su Complejidad Computacional. La complejidad teórica de un algoritmo se mide en unidades de tiempo a través del número de instrucciones (I₁, … I_n)  y del nº de veces (E₁, … E_v) que se ejecutan, además es independiente de la plataforma en la cual se corre el algoritmo. También sabemos que existen muchos parámetros de rendimiento que hacen que una instrucción se ejecute mejor en un procesador que en otro, o que los datos sean tan grandes que su movimiento tome una parte importante del tiempo de ejecución o que sea pararelizable, estos y otros condicionantes alteran los valores esperados.

• Estable. La estabilidad es la forma en cual se comportan los algoritmos cuando contienen valores idénticos, los algoritmos estables no cambian el orden relativo de los mismos.

• In Situ. Es el modo de cómo se utiliza la memoria respecto de las variables auxiliares, en este caso son los tipos de algoritmos que no requieren espacio adicional para realizar la clasificación, la unidad de medida es O (1). En la actualidad es un concepto en vías de desuso, no tiene sentido desperdiciar las mejoras que se pueden lograr usando memoria adicional, sobre todo cuando el coste de la memoria es despreciable.

• En Línea. Puede ordenar el vector a medida que lo recibe.

• Modelo. Es el método que utilizan los algoritmos para obtener la ordenación, pueden ser:
  • Distribución. Toman los elementos distribuyéndolos en varias estructuras intermedias que luego se reúnen y se concatenan.
  • Fusión.
  • Híbridos. Son los que utilizan dos o más algoritmos combinando sus características o utilizándolos en un orden determinado.
  • Inserción. Toma un elemento del vector, localiza la ubicación que le corresponde y lo inserta en esa posición.
  • Intercambio. Recorre el vector comparando los elementos adyacentes intercambiándolos si es necesario.
  • Selección. Necesita localizar el elemento de valor mínimo-máximo en el vector.

La mejor estructura de ordenación debería tener, al menos, las siguientes propiedades:

• Complejidad O (n lg n)
• Adaptativa
• Estable
• In Situ

Taxonomía.

Complejidad.

La mayoría de las publicaciones, incluida esta, muestran la complejidad de los algoritmos de ordenación en sus límites inferiores y superiores, representados mayoritariamente por valores O (–) que siempre se darán en función del tamaño n de la entrada (cantidad de elementos en el vector).

La estimación del límite inferior de un problema se mide en función del tamaño de la entrada y salida (n), esto nos permite decir que la ordenación no puede resolverse con ningún algoritmo menor de O (n), algo obvio, porque se necesitan al menos n pasos para leer y escribir los valores que se deben ordenar.

Por otro lado, sabemos que cualquier algoritmo debe comparar cada valor de entrada para reconocer si los valores están ordenados, lo podemos ver y representar como un árbol de decisión binario, siendo los nodos las comparaciones y las ramas los posibles resultados. Contamos las comparaciones de elementos como decisiones, pudiéndose observar que el número mínimo de hojas en el árbol es el factorial de n, entonces las hojas están en O (n log n), ya sabemos que el problema de la ordenación tiene los límites en O (n) y O (n log n).

El análisis de la complejidad que se hace de los algoritmos de ordenación se refiere a la situación inicial de los datos (rangos de los elementos, tamaño, ordenación inicial, etc.) que provoca las siguientes situaciones:

• Mejor caso Ω (–). La ejecución del algoritmo tiene una menor complejidad computacional. Por ejemplo, en el algoritmo de Inserción sucede cuando el conjunto de elementos a ordenar ya se encuentra ordenado y toma O (n) pasos para realizar la tarea.
• Peor caso O (–). La ejecución tiene una mayor complejidad computacional. Tomando el algoritmo de inserción, su peor caso sería cuando los elementos que le llegan están ordenados de forma inversa, necesitaría O (n ²) pasos para ordenarlos.
• Promedio Θ. Los datos a ordenar no siguen un patrón que aporte ventajas o desventajas, sería la situación normal de ejecución.

Continuar en Ordenación de Vectores II.