Buscar en el sitio
Contacto
Analisisdisenodealgoritmo
E-mail: miguel-762011@hotmail.com
TEMA 2
METODO DE ORDENACION
INTRODUCCIÓN
Dado un conjunto de n elementos a1, a2,..., an y una relación de orden total (≤) sobre ellos, el problema de la ordenación consiste en encontrar una permutación de esos elementos ordenada de forma creciente.
Aunque tanto el tipo y tamaño de los elementos como el dispositivo en donde se encuentran almacenados pueden influir en el método que utilicemos para ordenarlos, en este tema vamos a solucionar el caso en que los elementos son números enteros y se encuentran almacenados en un vector.
Si bien existen distintos criterios para clasificar a los algoritmos de ordenación, una posibilidad es atendiendo a su eficiencia. De esta forma, en función de la complejidad que presentan en el caso medio, podemos establecer la siguiente clasificación:
Burbuja, Inserción, Selección.
Mezcla, Montículos, Quicksort.
Incrementos , Cubetas , Residuos
ORDENACIÓN POR INSERCIÓN
El método de Inserción realiza n–1 iteraciones sobre el vector, dejando en la iésima etapa (2 ≤ i ≤ n) ordenado el subvector a[1..i]. La forma de hacerlo es colocando en cada iteración el elemento a[i] en su sitio correcto, aprovechando el hecho de que el subvector a[1..i–1] ya ha sido previamente ordenado. Este método puede ser implementado de forma iterativa como sigue:
PROCEDURE Insercion(VAR a:vector;prim,ult:CARDINAL);
VAR i,j:CARDINAL; x:INTEGER;
BEGIN
FOR i:=prim+1 TO ult DO
x:=a[i]; j:=i-1;
WHILE (j>=prim) AND (x
a[j+1]:=a[j]; DEC(j)
END;
a[j+1]:=x
END
END Insercion;
– En el caso medio, supondremos equiprobable la posición de cada elemento dentro del vector. Por tanto para cada valor de i, la probabilidad de que el elemento se sitúe en alguna posición k de las i primeras será de 1/i. El número de veces que se repetirá el bucle WHILE en este caso es (i–k), con lo cual el Número medio de operaciones que se realizan en el bucle es:
ORDENACIÓN 61
Por el modo en que funciona el algoritmo, tales casos van a corresponder a cuando el vector se encuentra ordenado de forma creciente, decreciente o aleatoria.
Como podemos ver, en este método los órdenes de complejidad de los casos peor, mejor y medio difieren bastante. Así en el mejor caso el orden de complejidad resulta ser lineal, mientras que en los casos peor y medio su complejidad es cuadrática.
Este método se muestra muy adecuado para aquellas situaciones en donde necesitamos ordenar un vector del que ya conocemos que está casi ordenado, como suele suceder en aquellas aplicaciones de inserción de elementos en bancos de datos previamente ordenados cuya ordenación total se realiza periódicamente.
2.3 ORDENACIÓN POR SELECCIÓN
En cada paso (i=1...n–1) este método busca el mínimo elemento del subvector
a[i..n] y lo intercambia con el elemento en la posición i:
PROCEDURE Seleccion(VAR a:vector;prim,ult:CARDINAL);
VAR i:CARDINAL;
BEGIN
FOR i:=prim TO ult-1 DO
Intercambia(a,i,PosMinimo(a,i,ult))
END
END Seleccion;
En cuanto a su complejidad, vamos a estudiar los casos mejor, peor y medio de
la llamada al procedimiento Seleccion(a,1,n), que van a coincidir con los mismos
casos (mejor, peor y medio) que los de la función PosMinimo.
En consecuencia, el algoritmo es de complejidad cuadrática.
Este método, por el número de operaciones de comparación e intercambio que realiza, es el más adecuado para ordenar pocos registros de gran tamaño. Si el tipo base del vector a ordenar no es entero, sino un tipo más complejo (guías telefónicas, índices de libros, historiales hospitalarios, etc.) deberemos darle mayor importancia al intercambio de valores que a la comparación entre ellos en la valoración del algoritmo por el coste que suponen. En este sentido, analizando el número de intercambios que realiza el método de Selección vemos que es de orden
O(n), frente al orden O(n2) de intercambios que presentan los métodos de Inserción
o Burbuja.
2.4 ORDENACIÓN BURBUJA
Este método de ordenación consiste en recorrer los elementos siempre en la misma dirección, intercambiando elementos adyacentes si fuera necesario:
PROCEDURE Burbuja (VAR a:vector;prim,ult:CARDINAL);
VAR i,j:CARDINAL;
BEGIN
FOR i:=prim TO ult-1 DO
FOR j:=ult TO i+1 BY -1 DO
IF (a[j-1]>a[j]) THEN
Intercambia(a,j-1,j)
END
END
END
END Burbuja;
El nombre de este algoritmo trata de reflejar cómo el elemento mínimo “sube”,
a modo de burbuja, hasta el principio del subvector.
Respecto a su complejidad, vamos a estudiar los casos mejor, peor y medio de
la llamada al procedimiento Burbuja(a,1,n).
En consecuencia, el algoritmo es de complejidad cuadrática.
Este algoritmo funciona de forma parecida al de Selección, pero haciendo más trabajo para llevar cada elemento a su posición. De hecho es el peor de los tres vistos hasta ahora, no sólo en cuanto al tiempo de ejecución, sino también respecto al número de comparaciones y de intercambios que realiza.
Una posible mejora que puede admitir este algoritmo es el control de la
existencia de una pasada sin intercambios; en ese momento el vector estará ordenado.
2.5 ORDENACIÓN POR MECLA (MERGESORT)
Este método utiliza la técnica de Divide y Vencerás para realizar la ordenación del vector a. Su estrategia consiste en dividir el vector en dos subvectores, ordenarlos mediante llamadas recursivas, y finalmente combinar los dos subvectores ya ordenados. Esta idea da lugar a la siguiente implementación:
PROCEDURE Mezcla(VAR a,b:vector;prim,ult:CARDINAL);
(* utiliza el vector b como auxiliar para realizar la mezcla *)
VAR mitad:CARDINAL;
BEGIN
IF prim
mitad:=(prim+ult)DIV 2;
Mezcla(a,b,prim,mitad);
Mezcla(a,b,mitad+1,ult);
Combinar(a,b,prim,mitad,mitad+1,ult)
END
END Mezcla;
2.6 ORDENACIÓN MEDIANTE MONTÍCULOS (HEAPSORT)
La filosofía de este método de ordenación consiste en aprovechar la estructura particular de los montículos (heaps), que son árboles binarios completos (todos sus niveles están llenos salvo a lo sumo el último, que se rellena de izquierda a derecha) y cuyos nodos verifican la propiedad del montículo: todo nodo es mayor o igual que cualquiera de sus hijos. En consecuencia, en la raíz se encuentra siempre el elemento mayor.
Estas estructuras admiten una representación muy sencilla, compacta y eficiente mediante vectores (por ser árboles completos). Así, en un vector que represente una
implementación de un montículo se cumple que el “padre” del i-ésimo elemento del vector se encuentra en la posición i÷2 (menos la raíz, claro) y sus “hijos”, si es que los tiene, estarán en las posiciones 2i y 2i+1 respectivamente.
PROCEDURE Monticulos(VAR a:vector;prim,ult:CARDINAL);
VAR i:CARDINAL;
BEGIN
HacerMonticulo(a,prim,ult);
FOR i:=ult TO prim+1 BY -1 DO
Intercambia(a,prim,i);
Empujar(a,prim,i-1,prim)
END
END Monticulos;
Los procedimientos Hacer Montículo y Empujar son, respectivamente, el que construye un montículo a partir del subvector a[prim..ult] dado, y el que “empuja” un elemento hasta su posición definitiva en el montículo, reconstruyendo la estructura de montículo en el subvector a[prim..ult–1]:
PROCEDURE HacerMonticulo(VAR a:vector;prim,ult:CARDINAL);
(* construye un monticulo a partir de a[prim..ult] *)
VAR i:CARDINAL;
BEGIN
FOR i:=(ult-prim+1)DIV 2 TO 1 BY -1 DO
Empujar(a,prim,ult,prim+i-1)
END
END HacerMonticulo;
PROCEDURE Empujar(VAR a:vector;prim,ult,i:CARDINAL);
(* empuja el elemento en posicion i hasta su posicion final *)
VAR j,k:CARDINAL;
BEGIN
k:=i-prim+1;
REPEAT
j:=k;
IF (2*j<=ult-prim+1) AND (a[2*j+prim-1]>a[k+prim-1]) THEN
k:=2*j
END;
IF (2*j
k:=2*j+1
END;
Intercambia(a,j+prim-1,k+prim-1);
UNTIL j=k
END Empujar;
2.7 ORDENACIÓN RÁPIDA DE HOARE (QUICKSORT)
Este método es probablemente el algoritmo de ordenación más utilizado, pues es muy fácil de implementar, trabaja bien en casi todas las situaciones y consume en general menos recursos (memoria y tiempo) que otros métodos. Su diseño está basado en la técnica de Divide y Vencerás, que estudiaremos en el siguiente capítulo, y consta de dos partes:
b) A continuación, los dos subvectores son ordenados mediante llamadas recursivas a Quicksort. Como los subvectores se ordenan sobre ellos mismos, no es necesario realizar ninguna operación de combinación.
Esto da lugar al siguiente procedimiento, que constituye la versión clásica del algoritmo de ordenación rápida de Hoare:
PROCEDURE Quicksort(VAR a:vector;prim,ult:CARDINAL);
VAR l:CARDINAL;
BEGIN
IF prim
l:=Pivote(a,a[prim],prim,ult);
Quicksort(a,prim,l-1);
Quicksort(a,l+1,ult)
END
END Quicksort;
La función Pivote parte del elemento pivote y permuta los elementos del vector
de forma que al finalizar la función, todos los elementos menores o iguales que el
pivote estén a su izquierda, y los elementos mayores que él a su derecha. Devuelve
la posición en la que ha quedado situado el pivote p:
PROCEDURE Pivote(VAR a:vector;p:INTEGER;prim,ult:CARDINAL)
:CARDINAL;
(* permuta los elementos de a[prim..ult] y devuelve una
posicion l tal que prim<=l<=ult, a[i]<=p si prim<=i
a[l]=p, y a[i]>p si l
de a[prim] *)
VAR i,l:CARDINAL;
BEGIN
i:=prim; l:=ult+1;
REPEAT INC(i) UNTIL (a[i]>p) OR (i>=ult);
REPEAT DEC(l) UNTIL (a[l]<=p);
WHILE i
Intercambia(a,i,l);
REPEAT INC(i) UNTIL (a[i]>p);
REPEAT DEC(l) UNTIL (a[l]<=p)
END;
Intercambia(a,prim,l);
RETURN l
END Pivote;
2.8 ORDENACIÓN POR INCREMENTOS (SHELLSORT)
La ordenación por inserción puede resultar lenta pues sólo intercambia elementos adyacentes. Así, si por ejemplo el elemento menor está al final del vector, hacen falta n pasos para colocarlo donde corresponde. El método de Incrementos es una extensión muy simple y eficiente del método de Inserción en el que cada elemento se coloca casi en su posición definitiva en la primera pasada. El algoritmo consiste básicamente en dividir el vector a en h subvectores:
a[k], a[k+h], a[k+2h], a[k+3h], ...
y ordenar por inserción cada uno de esos subvectores
(k=1,2,...,h–1).
Un vector de esta forma, es decir, compuesto por h subvectores ordenados
intercalados, se denomina h-ordenado. Haciendo h-ordenaciones de a para valores grandes de h permitimos que los elementos puedan moverse grandes distancias dentro del vector, facilitando así las h-ordenaciones para valores más pequeños de
h. A h se le denomina incremento.
Con esto, el método de ordenación por Incrementos consiste en hacer
h-ordenaciones de a para valores de h decreciendo hasta llegar a uno.
El número de comparaciones que se realizan en este algoritmo va a depender de
la secuencia de incrementos h, y será mayor que en el método clásico de Inserción (que se ejecuta finalmente para h = 1), pero la potencia de este método consiste en conseguir un número de intercambios mucho menor que con la Inserción clásica. El procedimiento presentado a continuación utiliza la secuencia de incrementos h = ..., 1093, 364, 121, 40, 13, 1. Otras secuencias pueden ser utilizadas, pero la elección ha de hacerse con cuidado. Por ejemplo la secuencia ..., 64, 32, 16, 8, 4, 2,
1 es muy ineficiente pues los elementos en posiciones pares e impares no son comparados hasta el último momento. En el ejercicio 2.7 se discute más a fondo esta circunstancia.
PROCEDURE Incrementos(VAR a:vector;prim,ult:CARDINAL);
VAR i,j,h,N:CARDINAL; v:INTEGER;
BEGIN
N:=(ult-prim+1); (* numero de elementos *)
h:=1;
ORDENACION
REPEAT h:=3*h+1 UNTIL h>N; (* construimos la secuencia *)
REPEAT
h:=h DIV 3;
FOR i:=h+1 TO N DO
v:=a[i]; j:=i;
WHILE (j>h) AND (a[j-h+prim-1]>v) DO
a[j+prim-1]:=a[j-h+prim-1];
DEC(j,h)
END;
a[j+prim-1]:=v;
END
UNTIL h=1
END Incrementos;
En cuanto al estudio de su complejidad, este método es diferente al resto de los procedimientos vistos en este capítulo. Su complejidad es difícil de calcular y depende mucho de la secuencia de incrementos que utilice. Por ejemplo, para la secuencia dada existen dos conjeturas en cuanto a su orden de complejidad: nlog2n y n1.25. En general este método es el escogido para muchas aplicaciones reales por ser muy simple teniendo un tiempo de ejecución aceptable incluso para grandes valores de n.
2.9 OTROS ALGORITMOS DE ORDENACIÓN
Los algoritmos vistos hasta ahora se basan en la ordenación de vectores de números enteros cualesquiera, sin ningún tipo de restricción. En este apartado veremos cómo pueden encontrarse algoritmos de orden O(n) cuando dispongamos de información adicional sobre los valores a ordenar.
2.9.1 Ordenación por Cubetas (Binsort)
Suponemos que los datos a ordenar son números naturales, todos distintos y comprendidos en el intervalo [1,n]. Es decir, nuestro problema es ordenar un vector con los n primeros números naturales. Bajo esas circunstancias es posible implementar un algoritmo de complejidad temporal O(n). Es el método de ordenación por Cubetas, en donde en cada iteración se sitúa un elemento en su posición definitiva:
PROCEDURE Cubetas(VAR a:vector);
VAR i:CARDINAL;
BEGIN
FOR i:=1 TO n DO
WHILE a[i]<>i DO
Intercambia(a,i,a[i])
END
END
END Cubetas;
2.9.2 Ordenación por Residuos (Radix)
Este método puede utilizarse cuando los valores a ordenar están compuestos por secuencias de letras o dígitos que admiten un orden lexicográfico. Éste es el caso de palabras, números (cuyos dígitos admiten este orden) o bien fechas.
El método consiste en definir k colas (numeradas de 0 a k–1) siendo k los posibles valores que puede tomar cada uno de los dígitos que componen la secuencia. Una vez tengamos las colas habría que repetir, para i a partir de 0 y hasta llegar al número máximo de dígitos o letras de nuestras cadenas:
1. Distribuir los elementos en las colas en función del dígito i.
2. Extraer ordenada y consecutivamente los elementos de las colas, introduciéndolos de nuevo en el vector.
Los elementos quedan ordenados sin haber realizado ninguna comparación.
Veamos un ejemplo de este método. Supongamos el vector:
[0, 1, 81, 64, 23, 27, 4, 25, 36, 16, 9, 49].
En este caso se trata de números naturales en base 10, que no son sino secuencias de dígitos. Como cada uno de los dígitos puede tomar 10 valores (del 0 al 9), necesitaremos 10 colas. En la primera pasada introducimos los elementos en las colas de acuerdo a su dígito menos significativo:
Cola 0 1 2 3 4 5 6 7 8 9
0 81,1 23 4,64 25 16,36 27 49,9
y ahora extraemos ordenada y sucesivamente los valores, obteniendo el vector:
[0, 81, 1, 23, 4, 64, 25, 16, 36, 27, 49, 9].
Volvemos a realizar otra pasada, esta vez fijándonos en el segundo dígito menos
significativo:
Cola 0 1 2 3 4 5 6 7 8 9
9,4,1,0 16 27,25,23 36 49 64 81
Volviendo a extraer ordenada y sucesivamente los valores obtenemos el vector
[0, 1, 4, 9, 16, 23, 25, 27, 36, 49, 64, 81]. Como el máximo de dígitos de los números a ordenar era de dos, con dos pasadas hemos tenido suficiente.
La implementación de este método queda resuelta en el problema 2.9, en donde se discute también su complejidad espacial, inconveniente principal de estos métodos tan eficientes.
DESCARGAR EL DOCUMENTO: