tmp

Uno de los problemas a resolver que provocó una discusión muy interesante (y puede que aún no esté terminada) en la creación de algoritmos fue la búsqueda de métodos que sirvan para realizar programas que ordenen la información. Por ejemplo, ordenar de mayor a menor (o al revés) una tabla a partir de una de sus columnas. Para simplificar el problema sólo trataremos el caso de ordenar las componentes de un vector. Los métodos más simples que permiten entender la complejidad del problema son el método de la Burbuja y el de la Selección. Pero a la hora hora de ordenar grandes cantidades de información son ambos desaconsejados por su lentitud e ineficiencia.

Swap

En algún punto de algoritmo que ordena, necesario intercambiar datos entre variables. Para no perder información utilizaremos una variable temporaria para realizar la tarea. Este mecanismo se conoce con el nombre de swap en los textos de computación. Típicamente en Fortran se usan las siguientes sentencias, pero en otros lenguajes hay órdenes que lo hacen directamente. Pasando de 3 órdenes a una sola.

Método de la Burbuja

Para entender el método consideremos que tenemos la información a ordenar en un vector. El método de la burbuja se basa en la idea de comparar sólo entre pares continuos e intercambiar los valores cuando cumplen con la condición deseada (mayor o menor valor según el orden que esté buscando). Este ciclo se tiene que repetir al menos n-1 veces si n es el número de elementos a ordenar. Pero se puede programar que si no se produce ningún cambio en uno de los ciclos (esto sucede cuando el vector ya quedó ordenado) que no se continue el proceso, ahorrando tiempo de la computadora. Por ejemplo, si pruebo ordenar un vector ya previamente ordenado el proceso terminaría con el primer ciclo.
Para testar si dejó de haber cambios, uso la variable lógica bandera en el programa. Esta variable toma el valor .true. mientras se siguen haciendo cambios y .false cuando ya el vector está ordenado. En este último caso el programa termina.
El programa que realiza esta tarea sería el siguiente y es relativamente sencillo:
\(\ \ \ \ \ \ \ \)subroutine bubble(n,a)

\(\ \ \ \ \ \ \ \)end
Este método tarda un tiempo que va como \(t \sim N^2\) en la peor situación y su eficiencia no es para nada buena, por no decir que es bastante mala. Se tiene como única ventaja que el algoritmo termina abruptamente si encuentra el vector ordenado.

Método de Selección

Si la información se encuentra en un vector, el método de selección se basa en la idea de tomar el primer elemento del vector y compararlo contra todos los otros elementos. Si ordenamos de mayor a menor y este primer elemento es menor que el elemento contra el cual estoy comparando lo cambio por este. Una vez hecho este cambio sigo ahora comparando mi nuevo primer elemento contra los otros elementos restantes, continuando con la idea de que cada vez se cumpla con encontrar otro menor se vuelve a realizar el cambio.
Una vez terminada la comparación del primer elemento tomo el segundo y así continuo el proceso de comparación contra los elementos restantes. Este ciclo termina cuando comparo el anteúltimo elemento contra el último. Con este algoritmo se va coleccionando los elementos más grandes en los primeros elementos del vector.
El tiempo que tarda este procedimiento es proporcional a \(t \sim N^2\) (donde N es la cantidad de elementos a ordenar). Por lo tanto, el tiempo crece muy rápido si se aumenta la cantidad de elementos a ordenar. Por ejemplo, si duplico la cantidad de elementos a ordenar tardaré 4 veces más, pero en el caso de tener 10 veces más elementos tardaré 100 veces más en obtener un resultado útil. No es un método aconsejable para usar en una situación real, pero tiene utilidad académica, ya que sirve para entender los procesos y problemas involucrados en los algoritmos usados para ordenar.

El programa que realiza esta tarea sería el siguiente:
\(\ \ \ \ \ \ \ \)subroutine selec(n,a)

Este método no es muy eficiente ya que no descubre si el vector ya estaba ordenado de antemano y recorre probando todas las combinaciones posibles.

Método de Selección mejorado

La idea es no realizar el swap todo el tiempo, sino sólo con el elemento mayor encontrado, por lo cual se guarda el índice del elemento a hacer el swap hasta el final del ciclo, por lo cual se ahorra tiempo de cómputo.
El programa que realiza esta tarea sería el siguiente:
\(\ \ \ \ \ \ \ \)subroutine selec(n,a)

\(\ \ \ \ \ \ \ \)end
Esta versión es un poco más eficiente que la anterior porque realiza menos operaciones de intercambio (swap). Pero por otro lado, no descubre el caso de que el vector ya estaba ordenado de antemano y por lo tanto no tendría que hacer el análisis de la totalidad de la muestra de datos.

Otros Métodos

Hay otros métodos que son mejores. Veremos algunos de ellos, pero no con profundidad. Para el lector con mayor interés en el tema se puede consultar el libro Numerical Recipes (ya nombrado anteriormente). Este libro se puede consultar aquí. El texto consta de explicaciones de los algoritmos primero en forma teórica y luego práctica, en la cual se incluye la subrutina del método escrita en Fortran. En este libro hay mucha información detallada con explicaciones y evaluaciones de la eficiencia de los métodos que nombraremos y otros más que no discutiremos en este apunte.

Inserción Directa (Straight Insertion)

Este método viene del modo más simple de ordenar un mazo de cartas. Se toma la segunda baraja y se la compara con la primera, si hay que cambiarla, se la cambia. Se toma la tercera y se compara con la segunda y luego con la primera. Se sigue así hasta la última carta. Hay que notar que no es necesario comparar contra todas las cartas, solo hasta que se encuentre el lugar que le corresponde, lo que ahorra tiempo de computación. Este método va con \(N^2\) (en el caso extremo) y se aconseja su uso para muestras pequeñas (\(\sim N < 20\)). Se lo utiliza como apoyo de otros algoritmos para ordenar subgrupos parciales de un grupo mayor, porque para pocos elementos es eficiente y rápido.

Método de las cáscaras (Shell´s Method)

Esta es en sí una variante del método anterior. La idea es dividir la muestra en grupos de a dos, ordenar estos elementos en el grupo de a dos usando inserción directa. Y luego juntar en ahora grupos de 4 elementos ordenar y juntar en grupos del doble de elementos y repetir el proceso. Se puede mostrar que en promedio en este método el tiempo va como \(t \sim N^{1.25}\) al menos para \(N<60000\). El truco de este algoritmo es que se puede ordenar muy rápido grupos de pocos elementos y si junto grupos que ya están algo ordenados el algoritmo tiene pocas veces que cambiar elementos de lugar, es decir aumento la probabilidad de que un elemento ya esté en su lugar. Y por ello en promedios el método es más rápido que \(N^2\).

Quicksort

Este método es el más rápido conocido para muestras muy grandes que se necesitan ordenar, la idea es que la muestra se parte en dos pedazos y un elemento en particular (el \(a\)) es el seleccionado para separar estas dos particiones. Los elementos son chequeados en pares dejando en una muestra los elementos \(\leq\) a la izquierda y en la otra los \(\geq\) a la derecha, por lo tanto \(a\) queda en su lugar. El proceso se vuelve a repetir con la partición de la izquierda y luego con la de la derecha. Para realizar toda esta tarea el algoritmo requiere algo más de memoria, pero es extremadamente eficiente. Este método es algo mejor que otro método conocido como Heapsort que también muestra un excelente desempeño para grandes valores de \(N\).

Probando métodos

Para probar los distintos métodos haremos un programa que ordene un vector de elementos al azar y mediremos los tiempos de cada algoritmo y su implementación. Es importante señalar que los distintos métodos, tienen distintos resultado según las características de los datos de entrada. Puede haber datos desordenados al azar (como lo que vamos a usar en el ejemplo), datos con cierto grado de ordenamiento y datos que estén completamente invertidos en su distribución, es decir, quiero ordenar de menor a mayor pero los datos originales están ya ordenados de mayor a menor (o parcialmente ordenados). La eficiencia de los algoritmos puede en si cambiar bastante según esta distribución de datos de entrada.
Para esto utilizaremos las rutinas del método de selección y el de la burbuja que hemos visto, y las demás implementaciones serán del Numerical Recipes. La tabla 1 muestra los tiempos que tarda en hacer los cálculos cada uno de los algoritmos descriptos sobre la misma muestra. En la figura [fig:qr_sort] puede verse una comparación de distintos métodos como animación en tiempo real de ellos.

Resultados obtenidos para una muestra de números al azar, la cual se la ordena con cada algoritmo y se le toma el tiempo. Cada una de estas implementaciones recibió exactamente la misma muestra. Note que los dos primeros métodos van \(N^2\) y que al multiplicar por 10 la muestra, estoy tardando 100 veces más en correr el algoritmo (\(10^2=100\)).
Algoritmo	\(10^5\) números	\(10^6\) números
	segundos	segundos
Burbuja	36.07	3678.71
Selección	25.95	2547.27
Inserción Directa	6.56	646.6
Cáscaras	0.02	0.3
Heapsort	0.02	0.19
Quicksort	0.01	0.12

Ordenar pares ordenados

Si tengo pares ordenados (\(X_i\),\(Y_i\)) y por ejemplo los ordeno por los valores \(X_i\). Es necesario que los pares ordenados no se destruyan o sea que cada \(X_i\) siga asociados a su \(Y_i\). Para resolver este problema deberé agregar a la subrutina no importa cual sea el método que cuando cambio el elemento \(X_i\) cambie también el \(Y_i\), de esta manera:
\(\ \ \ \ \ \ \ \)\(\vdots\)

\(\ \ \ \ \ \ \ \)\(\vdots\)
El “algo” que aparece en el IF dependerá del algoritmo a utilizar.

Ordenar sin modificar el vector inicial

Una posibilidad es ordenar pero sin modificar el vector inicial y sin copiarlo a otro vector. Para hacer esta tarea creamos un vector de índices, donde el primer elemento tiene un 1, el segundo un 2 y así hasta los N valores que sean necesarios.
Si A es el vector a ordenar e I es un vector de índices, puede referirse a los elementos de A como A(I(j)), es decir cada elemento de A, será el elemento i(j). Entonces en vez de ordenar el vector A, modifico los índices del vector I y de esta manera puedo mantener la configuración inicial de A y también la forma ordenada como A(i(j)).
Es decir haríamos:
\(\ \ \ \ \ \ \ \)\(\vdots\)

Subrutinas del sistema - getenv(), getargs() y systems()

Estas son llamadas a subrutinas del propio sistema operativo y son muy útiles.
GETARG() permite ingresar datos para las variables en el mismo renglón que se llama al programa, mientras que GETENV() permite obtener parámetros del ambiente del usuario (ejemplo, su nombre, directorio en el que está, etc).
Para GETARG() tenemos que dar como argumentos el número de la variable que voy a leer en la línea de programa y una variable de caracter donde quedará escrita esa variable.
En cambio para GETENV() deberé indicar el nombre de la variable de ambiente que leo y una variable de caracter donde quedarán escritos esos datos.
Ejemplo:
\(\ \ \ \ \ \ \ \)program prueba

\(\ \ \ \ \ \ \ \)end
Y si compilo y luego corro el programa así:
./prueba 22
obtengo como resultado:
Username=carlos
Argument=22

CALL SYSTEM()

Esta llamada permite dar órdenes al sistema operativo con los comandos de texto como si fuesen escritos en una terminal. Saber usar esta llamada tiene muchas ventajas. Normalmente existen más de 3000 comandos en una instalación simple de LINUX. Y muchos cubren la mayoría de las necesidades domésticas, como transformar archivos de formatos, etc. En resumen, un programa Fortran puede darle órdenes al sistema operativo.
Por ejemplo, si quiero que mi programa lea del directorio los archivos que terminen en “.dat” para después procesarlos haría:

Algoritmos para ordenar (Sort)