PDF de programación - Capítulo 2 - ORDENACIÓN

Capítulo 2

ORDENACIÓN

2.1 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:



• Θ(n2): Burbuja, Inserción, Selección.
• Θ(nlogn): Mezcla, Montículos, Quicksort.
• Otros: Incrementos Θ(n1.25), Cubetas Θ(n), Residuos Θ(n).



En el presente capítulo desarrollaremos todos ellos con detenimiento, prestando
especial atención a su complejidad, no sólo en el caso medio sino también en los
casos mejor y peor, pues para algunos existen diferencias significativas. Hemos
dedicado también una sección a problemas, que recogen muchas de las cuestiones y
variaciones que se plantean durante el estudio de los distintos métodos.
Como hemos mencionado anteriormente, nos centraremos en la ordenación de
enteros, muchos de los problemas de ordenación que nos encontramos en la
práctica son de ordenación de registros mucho más complicados. Sin embargo este
problema puede ser fácilmente reducido al de ordenación de números enteros
utilizando las claves de los registros, o bien índices. Por otro lado, puede que los
datos a ordenar excedan la capacidad de memoria del ordenador, y por tanto deban
residir en dispositivos externos. Aunque este problema, denominado ordenación
externa, presenta ciertas dificultades específicas (véase [AHO87]), los métodos
utilizados para resolverlo se basan fundamentalmente en los algoritmos que aquí
presentamos.

58

TÉCNICAS DE DISEÑO DE ALGORITMOS

Antes de pasar a desarrollar los principales algoritmos, hemos considerado
necesario precisar algunos detalles de implementación.
• Consideraremos que el tamaño máximo de la entrada y el vector a ordenar

vienen dados por las siguientes definiciones:


CONST n =...; (* numero maximo de elementos *)
TYPE vector = ARRAY [1..n] OF INTEGER;


• Los procedimientos de ordenación que presentamos en este capítulo están
diseñados para ordenar cualquier subvector de un vector dado a[1..n]. Por eso
generalmente poseerán tres parámetros: el nombre del vector que contiene a los
elementos (a) y las posiciones de comienzo y fin del subvector, como por
ejemplo Seleccion(a,prim,ult). Para ordenar todo el vector, basta con invocar al
procedimiento con los valores prim= 1, ult = n.

• Haremos uso de dos funciones que permiten determinar la posición de los

elementos máximo y mínimo de un subvector dado:


PROCEDURE PosMaximo(VAR a:vector;i,j:CARDINAL):CARDINAL;
(* devuelve la posicion del maximo elemento de a[i..j] *)

VAR pmax,k:CARDINAL;
BEGIN
pmax:=i;
FOR k:=i+1 TO j DO
IF a[k]>a[pmax] THEN
pmax:=k
END
END;
RETURN pmax;
END PosMaximo;

PROCEDURE PosMinimo(VAR a:vector;i,j:CARDINAL):CARDINAL;
(* devuelve la posicion del minimo elemento de a[i..j] *)

VAR pmin,k:CARDINAL;
BEGIN
pmin:=i;
FOR k:=i+1 TO j DO
IF a[k]<a[pmin] THEN
pmin:=k
END
END;
RETURN pmin;
END PosMinimo;



ORDENACIÓN



59

• Y utilizaremos un procedimiento para intercambiar dos elementos de un vector:


PROCEDURE Intercambia(VAR a:vector;i,j:CARDINAL);
(* intercambia a[i] con a[j] *)
VAR temp:INTEGER;
BEGIN
temp:=a[i];
a[i]:=a[j];
a[j]:=temp
END Intercambia;


Veamos los tiempos de ejecución de cada una de ellas:



a) El tiempo de ejecución de la función PosMaximo va a depender, además del
tamaño del subvector de entrada, de su ordenación inicial, y por tanto
distinguiremos tres casos:
– En el caso mejor, la condición del IF es siempre falsa. Por tanto:

T(n) = T(j – i + 1) = 1 +

j


∑




k =i +1

(3 + 3)





 + 1 = 5 + 6(j − i).
+ 3


– En el caso peor, la condición del IF es siempre verdadera. Por consiguiente:

T(n) = T(j – i + 1) = 1 +

j


∑




k =i +1


(3 + 3 +1)



 + 1 = 5 + 7(j − i).
+ 3


– En el caso medio, vamos a suponer que la condición del IF será verdadera en

el 50% de los casos. Por tanto:

T(n) = T(j – i + 1) =

1

j


+ ∑







33(
+=
ik
1

++

1
2

)


+


3





+=+

51

13
2

(

j

−

i

)

.

Estos casos corresponden respectivamente a cuando el elemento máximo se
encuentra en la primera posición, en la última y el vector está ordenado de
forma creciente, o cuando consideramos equiprobables cada una de las n
posiciones en donde puede encontrarse el máximo.

Como podemos apreciar, en cualquiera de los tres casos su complejidad es lineal

con respecto al tamaño de la entrada.



b) El tiempo de ejecución de la función PosMinimo es exactamente igual al de la

función PosMaximo.



c) La función Intercambia realiza 7 operaciones elementales (3 asignaciones y 4

accesos al vector), independientemente de los datos de entrada.

60

TÉCNICAS DE DISEÑO DE ALGORITMOS

Nótese que en las funciones PosMaximo y PosMinimo hemos utilizado el paso
del vector a por referencia en vez de por valor (mediante el uso de VAR) para evitar
la copia del vector en la pila de ejecución, lo que incrementaría la complejidad del
algoritmo resultante, pues esa copia es de orden O(n).

2.2 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]) DO
a[j+1]:=a[j]; DEC(j)
END;
a[j+1]:=x
END
END Insercion;


Para estudiar su complejidad, vamos a estudiar los casos mejor, peor y medio de
la llamada al procedimiento Insercion(a,1,n).



– En el caso mejor el bucle interno no se realiza nunca, y por tanto:

T(n) =





n

(
)
+++∑
3443

=

2

i


=+
3


14

n

−

11

.

– En el caso peor hay que llevar cada elemento hasta su posición final, con lo que

el bucle interno se realiza siempre de i–1 veces. Así, en este caso:

T(n) =






n

++∑
43






=

2

i

i

−
1

∑

=
1

j





+

)54(





++

31











=+

3

9
2

+

2

n

13
2

−

n

10

.

– 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

1
i





i

(
−∑
i

9

=
1

k

k

)

=+


4

9
2

−

i

1
2

.

Por tanto, el tiempo de ejecución en el caso medio es:

T(n) =





n

++∑
43





=

2

i

−

i

9
2





1
2


+


3









=+

3

+

2

n

9
4

47
4

−

n

11

.

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 el caso mejor:
(
13

nT
)(

−
1

n

++


= ∑



=
1

i



(
(65

+

−
in

)

)

++

71

)


=+
3


2

n
3

+

14

n

−

.14



62

TÉCNICAS DE DISEÑO DE ALGORITMOS

– En el caso peor:
(
13

nT
)(

−
1

n

++


= ∑



=
1

i

– En el caso medio:

(
(75

+

−
in

)

)

++

71

)

=+
3


7
2

+

2

n

27
2

−

n

.14



−
1

n

=
1

i

+



(

)





−

n

+

5

2

n













.14

=+

3

nT
)(

−
in

55
4

++

13

13
2


= ∑




++
71


13
4
En consecuencia, el algoritmo es de complejidad cuadrática.
Este método,