Make your own free website on Tripod.com

ALGORTIMOS DE ORDENACION

Generalmente, se considera ordenar (clasificar) el proceso de reorganización de un conjunto dado de objetos en una secuencia especificada. El objetivo de este proceso es facilitar la búsqueda posterior de los elementos del conjunto ordenado. La búsqueda de información es una operación básica en el proceso de datos, de ahí que por extensión, la ordenación se convierta también en una actividad fundamental en dicho procesamiento de datos.

El tema de la ordenación es idóneo para mostrar como los problemas se pueden resolver utilizando una gran variedad de algoritmos, todos con el mismo objetivo, pero cada uno presentando ciertas ventajas sobre los otros. Resulta un tema interesante para enfatizar la necesidad de analizar el funcionamiento de los algoritmos.

Normalmente, la clasificación se divide en interna o externa. El concepto de ordenación interna hace referencia a que el soporte donde se realiza la ordenación es la memoria principal del ordenador. Cuando el número de elementos que se desea clasificar es demasiado grande para caber en memoria y se encuentra en un archivo, entonces se habla de ordenación externa.

En esta página se tratara exclusivamente el problema de la ordenación interna.

Normalmente, la función de ordenación viene explícitamente reflejada en los objetos a ordenar como un campo de información mas sobre cada elemento. De manera que, en general, cada elemento del conjunto tendrá más de un campo de información (estructura de registro) y uno de esos campos indicará como se clasifican los elementos. El campo que especifica la relación de orden recibe el nombre de clave. El problema de la clasificación consiste entonces en ordenar una secuencia de registros de manera que sus claves formen una cadena no decreciente.

Cuando se trabaja con arrays, la principal condición a imponer sobre los métodos de ordenación es la utilización eficiente de la memoria disponible. Como el tamaño de los arrays a ordenar puede resultar, en general, grande, es necesario implementar algoritmos que realicen permutaciones de elementos utilizando únicamente el espacio dedicado para ese array.

Una vez supuesta la utilización conveniente de la memoria, los siguientes criterios para evaluar los algoritmos de ordenación hacen referencia al número de operaciones básicas que deben realizar. Una buena medida de eficiencia se obtiene en base al número de comparaciones entre las claves de los elementos (C) y al movimiento de elementos (M). Estos dos valores dependerán del número n de elementos a ordenar (tamaño del array). Los algorimos de ordenación más eficientes (QuickSort, MergeSort, HeapSort) tienen una complejidad de O(n*lg(n)). Los algoritmos de ordenación más simples, los llamados métodos directos (inserción, selección y burbuja), presentan una complejidad de orden 'n cuadrado' O(n^2).

En la descripción de los siguientes algoritmos de ordenación se va a suponer, para simplificar la notación empleada, que la única información asociada con cada uno de los elementos del array es la clave por la cual se ordena. Esto no va a restar generalidad al proceso, ya que, como se ha comentado anteriormente, de existir mas información asociada con cada elemento, ésta resultaría irrelevante durante el proceso de ordenación.

Animaciones de Algoritmos de Ordenación
Esta animación fue escrita por: David Eck
(Disculpe, su browser no soporta Java!)

Ordenación por inserción directa

En este método se considera que en todo momento se tiene la secuencia de elementos a ordenar dividida en dos subsecuencias, la primera de ellas, A(1), A(2), .. ,A(i-1) ya ordenada, y la segunda, A(i), .. ,A(n), con los elementos que faltan por ordenar. En cada paso, empezando con i=2, e incrementando el valor de i de uno en uno, se toma el elemento i del array y se inserta en el sitio adecuado dentro de la subsecuencia ordenada. El caso i=1 no se tiene en cuenta pues se considera que el primer elemento esta ordenado respecto a si mismo.

Cuando se considera el segundo elemento (i=2) se trata de ubicarlo corréctamente respecto a lo que ya esta ordenado (un único elemento), lo que implica simplemente una comparación. A medida que el tamaño de la subsecuencia ordenada aumenta, se incrementa el número de comparaciones necesarias para insertar un elemento. La inserción de cada elemento implica ir comparando y desplazando secuencialmente un elemento respecto a todos los anteriores hasta encontrar su posición correcta en el array. El criterio de finalización del proceso de inserción de un elemento es doble: que se encuentre un elemento con clave menor que el que se desea insertar (suponiendo comparaciones desde el final de la secuencia ordenada) o bien, que se llegue al principio de la secuencia sin encontrar ningun elemento menor. En cuyo caso la posición correcta del elemento sera la primera.

Algoritmo Insercion

/* InsertionSort para Enteros */

  void insercion( int A[], int n ) {
  /* Pre-condicion: a contiene n elementos a ser ordenados */
    int i, j, v;

    /* Inicialmente, el primer elemento se considera 'ordenado' */
    /* i divide el arreglo a en una región ordenada, x<i, 
       y una región no ordenada, x >= i */
    
    for(i=1;i<n;i++) {
        /* Selecciona el elemento en el inicio de la región no ordenada */
        v = A[i];
        /* Recorre hacia atrás el arreglo, buscando  
           la posición correspondiente a v */
        j = i;
        /* Si este elemento es mayor que v, moverlo hacia arriba */
        while ( A[j-1] > v ) {
          A[j] = A[j-1]; j = j-1;
          if ( j <= 0 ) break;
          }
        /* Se detiene cuando A[j-1] <= v, colocando a v en la posición j */
        A[j] = v;
        }
    }    

Análisis del algoritmo

En el mejor de los casos, el array estará inicialmente ordenado, entonces el bucle interno (mientras) sólo ejecuta el paso de comparación, que siempre será falso. Esto implica que en el mejor de los casos el número de comparaciones sera n-1. Además, el número de asignaciones será fijo para cada iteración y, por tanto, el coste asociado será lineal con n.

En el peor de los casos, el array está inversamente ordenado y el número de comparaciones y asignaciones a realizar será máximo. En este caso, el número de pasos a realizar por el algoritmo es proporcional a 'n cuadrado'.

En el caso medio, el algoritmo de inserción directa, tanto en el número de comparaciones como en el número de asignaciones es de orden cuadrático.

Ordenación por selección directa

En este segundo método se continua con la idea de dividir el array en dos secuencias (una ordenada y otra no), pero varía la forma en que va creciendo la secuencia ordenada. El método consiste en seleccionar el elemento con clave mínima dentro de la secuencia desordenada e intercambiarlo con el elemento que ocupa el primer lugar de esa secuencia. Al iniciarse el proceso, la secuencia desordenada abarca todo el array, se selecciona el mínimo y se intercambia con el elemento A[1], con lo cual ya se tiene el primer elemento de la secuencia ordenada en su lugar, a continuación se repite la operacion con los n-1 elementos que faltan por ordenar, consiguiendose así colocar correctamente A[2]. El proceso se repite hasta colocar los n elementos.

El algoritmo sería:

Algoritmo Seleccion

/* SelectionSort para Enteros */

  void seleccion( int A[], int n ) {
  /* Pre-condicion: A contiene n elementos a ser ordenados */

     int x,i,j,k;

     for( i=1; i <n-1; i++){
       x = A[i];
       k = i;

       /* buscar el minimo desde i+1 a n */
       for( j =i+1; j <n; j++){  
         if (A[j] < x){
            k = j;            /* guarda el indice del minimo */
            x = A[j];         /* guarda el valor del minimo  */
         }        
       }

      A[k] = A[i];            /* intercambiamos valores */
      A[i] = x;

     }
  } 
  
El algoritmo de inserción directa buscaba la posición correcta de un elemento dado, el método de selección, por el contrario, busca el elemento que debe ocupar una determinada posición en el array ordenado. En este sentido los dos algoritmos siguen filosofias de trabajo opuestas.

Análisis del algoritmo

El número de comparaciones realizadas por el algoritmo resulta independiente de la ordenación inicial del array (hay que tener en cuenta que el número de iteraciones a realizar está prefijado, y es de orden cuadrático.

El número de asignaciones, por su parte, si que depende de la ordenación inicial. En el mejor de los casos (array ordenado), hay que realizar 3(n-1) asignaciones sobre elementos del array, dependencia lineal con n. Sin embargo, en el peor de los casos y en el caso promedio, de nuevo, este algoritmo tiene que realizar un número de asignaciones proporcional a 'n cuadrado'.

En general, el algoritmo de selección directa resulta preferible al de inserción, aunque en los casos en los que el array esta prácticamente ordenado puede resultar más eficiente el método de inserción.

3. Ordenación por intercambio directo (Burbuja)

El método de intercambio directo, también conocido como método de la burbuja, tiene como caracteristica dominante el intercambio entre elementos del array. La idea consiste en comparar e intercambiar, si es necesario, pares de elementos adyacentes hasta que todos esten ordenados. Normalmente, el proceso de comparación e intercambio se lleva a cabo comenzando por el final del array, pasando por todas las posiciones del mismo y comparando cada una de ellas con la anterior, si la ubicación relativa de los dos elementos comparados es correcta (el menor delante del mayor) se pasa a comparar otro par, sino es asi, se intercambian los dos valores.

Este proceso se debe realizar recorriendo repetidamente el array, consiguiendose colocar, por lo menos, en cada iteración un elemento en su posición correcta. El algoritmo sería:

Algoritmo Burbuja

/* Ordenación Burbuja para enteros */

  #define SWAP(a,b)   { int t; t=a; a=b; b=t; }

  void burbuja( int A[], int n )
  /* Pre-condicion: A contiene n elementos a ser ordenados */
  {
    int i, j;

    for(i=0;i<n;i++)
        {
        /* Recorre el arreglo desde el primer elemento hasta 
           el final de la región no ordenada */
        for(j=1;j<(n-i);j++)
           {
           /* Si elementos adjacentes están fuera de orden, se intercambian */
           if( A[j-1]>A[j] ) SWAP(A[j-1],A[j]);
           }
        }
    }    
  

Análisis del algoritmo

El número de comparaciones que realiza el algoritmo es fijo y proporcional a 'n cuadrado'. El número de asignaciones es 0 si el array está ordenado (caso más favorable) y proporcional a 'n cuadrado' en el caso peor y promedio. Con lo que de nuevo, este método de ordenación tiene una dependencia cuadrática con el tamaño del array, como los anteriores.

En general, el método de intercambio directo proporciona peores resultados que los otros dos métodos comentados. Sin embargo, la idea del intercambio de pares de elementos cuando se realiza entre posiciones no adyacentes del array da lugar a uno de los mejores métodos de ordenación conocidos, el método Quicksort (más conocido como Qsort).

El método de intercambio admite una serie de mejoras evidentes. Por ejemplo, resulta bastante sencillo detener el algoritmo cuando el array ya esté ordenado. Bastaría con detectar que en una determinada iteración no se realiza ningun intercambio de elementos, esto indica que todos ellos están corréctamente organizados y que, por tanto no es necesario realizar ninguna iteración más. Además, el algoritmo de intercambio, tal como ha sido especificado, permite colocar rápidamente los elementos de menor clave pero, sin embargo, no resulta igual de eficiente a la hora de situar los elementos grandes. Esto es debido a que todas las comparaciones se realizan partiendo del final del array, lo que permite ir 'subiendo' fácilmente los elementos pequeños hacia las posiciones iniciales del array. Este comportamiento no simétrico del método de ordenación se puede corregir parcialmente alternando el sentido de las iteraciones, es decir, haciendo que tras una iteración partiendo del final de array se realice otra que parta del inicio. De esta manera se compensa el comportamiento del algoritmo respecto a todos los elementos. Esta ultima modificacion del algoritmo de intercambio recibe el nombre de metodo de la sacudida.

En cualquier caso, las modificaciones comentadas sobre el algoritmo de intercambio no mejoran sustancialmente el método y solamente resultan verdaderamente útiles en casos muy concretos.

Estudio comparativo de los algoritmos directos de ordenación

Para terminar el capítulo se va a realizar una comparación cuantitativa de los métodos de ordenación introducidos. Este estudio intenta poner de manifiesto, una vez mas, la diferencia que existe entre diversos algoritmos que, aunque teniendo la misma finalidad, resuelven los problemas utilizando un punto de vista diferente.

La primera comparación mostrará la dependencia de los resultados de los algoritmos de ordenación con el tamaño del vector a ordenar. En el primer ejemplo se dan tiempos de ejecución para distintos algoritmos aplicados primero sobre un vector de n=256 elementos y posteriormente sobre n=512. Para este caso se supone que los datos del vector son simples y estan formados únicamente por la clave de ordenación.

En la siguiente tabla se dan tiempos de ejecución en milisegundos sobre los dos tipos de vectores descritos (la columna derecha corresponde al vector de 512 elementos). Para tener una referencia respecto a otros tipos de algoritmos mas eficientes, se incluyen los datos del algoritmo QuickSort.

Algoritmo Ordenado Aleatorio Inversamente ordenado
Inserción 12    23 366    1444 704    2836
Selección 489    1907 509    1956 695    2675
Burbuja 540    2156 1026    4054 1492    5931
Quicksort 31    69 60    146 37    79

La comparación más significativa viene dada por la columna que indica los tiempos de ejecución cuando el array está aleatoriamente ordenado. En este caso, se puede comprobar que los tiempos de los métodos de inserción y selección son relativamente comparables (algo mejor el primero que el segundo), mientras que el método de intercambio es claramente peor, duplicando los tiempos de ejecución de los anteriores algoritmos. Ademas, se puede comprobar que, en cualquier caso, los métodos directos son mucho peores que el Qsort.

Los casos en los que el array está inicialmente ordenado o inversamente ordenado, resultan situaciones demasiado particulares y no proporcionan datos para una comparación significativa.

En una segunda comparación vamos a ver como influye el hecho de tener vectores donde los elementos poseen varios campos de información. Se sabe que una de las operaciones básicas para ordenar un vector es el movimiento de información entre componentes del vector. El coste real asociado con estas asignaciones depende claramente de la cantidad de información que tenga asociada cada elemento del array. Al incrementar la información manejada, resultarán más convenientes aquellos algoritmos que realicen un número menor de intercambios de elementos.

En la siguiente tabla se comparan los tiempos de ejecución de los algoritmos (mseg) cuando se aplican sobre el array de 256 del ejemplo anterior (donde la única información es la clave de ordenación) y sobre otro array del mismo tamaño, pero donde cada elemento lleva asociada una información adicional que ocupa siete veces el espacio de la clave.

Algoritmo Ordenado Aleatorio Inversamente ordenado
Inserción 12    46 366    1129 704    2150
Selección 489    547 509    607 695    1430
Burbuja 540    610 1026    3212 1492    5599
Quicksort 31    55 60    137 37    75

En este caso, continua cumpliendose que el método de la burbuja es el peor de los métodos y que los resultados del Qsort son muy superiores al del resto de los algoritmos. Sin embargo, ahora aparecen diferencias apreciables entre los métodos de inserción y selección. Como el método de selección necesita mover menos elementos para ordenar el array, resulta que el tiempo de ejecucion es significativamente menor que el del método de inserción.