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 |
|
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.
/* 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;
}
}
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.
El algoritmo sería:
/* 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.
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.
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:
/* 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]);
}
}
}
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.
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.