PDF de programación - Parte II: Estructuras de datos y algoritmos - 3. Métodos de ordenación.

Parte II: Estructuras de Datos y
Algoritmos

UNIVERSIDAD DE CANTABRIA

1. Introducción al análisis y diseño de algoritmos.
2. Tipos abstractos de datos.
3. Métodos de ordenación.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

4

© Javier Gutiérrez, Michael González

24/nov/08

1

Notas:

UNIVERSIDAD DE CANTABRIA

3. Métodos de ordenación.

• El modelo de ordenación interna.
• Esquemas simples de ordenación.
• Ordenación Rápida.
• Ordenación por Cajas.
• Ordenación por Base.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

2

3.1. El modelo de ordenación
interna.

UNIVERSIDAD DE CANTABRIA

Los procesos de ordenación pueden ser:
• internos: para ordenar datos en la memoria del computador
• externos: para ordenar datos que residen en memoria

secundaria (ficheros)

Los objetos a ser ordenados son de cualquier tipo, aunque
deben tener definida la operación de comparación estándar
(<).
• en Ada se puede redefinir esta operación
• en otros lenguajes, o también en Ada, se pueden ofrecer

mediante funciones definidas al efecto

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

3

Notas:

UNIVERSIDAD DE CANTABRIA

Los procesos de ordenación de listas de objetos, de acuerdo con una relación de orden lineal, son
tan importantes y frecuentes que su análisis es de gran importancia.

Los procesos de ordenación pueden ser de dos tipos:

• Ordenación interna. Se realiza en la memoria del computador.
• Ordenación externa. Cuando el volumen de información es muy grande y no cabe en la

memoria principal del computador, es preciso manejar la información en la memoria
secundaria o masiva. En este caso el cuello de botella es el movimiento de datos entre la
memoria principal y la secundaria, por lo que es preciso tener en cuenta técnicas especiales.

En este capítulo se analizarán algunos métodos de ordenación interna. Los objetos a ser ordenados
pueden ser de cualquier tipo, siempre que exista una relación de orden lineal entre ellos.
Supondremos que estos objetos tienen su relación de orden definida por medio de las operaciones
de comparación del Ada (<). En caso de que los objetos no tengan esta relación predefinida, se
escribirá por parte del usuario. En otros lenguajes, será necesario escribir una función para realizar
esta operación de comparación.

El problema de la ordenación es organizar la secuencia de registros r1, r2, ..., rn, obteniéndose la
secuencia ri1, ri2, ..., rin, tal que ri1 ≤ ri2 ≤ ... ≤ rin.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

4

3.2. Esquemas simples de
ordenación

UNIVERSIDAD DE CANTABRIA

Supondremos que hay que ordenar N elementos del array A

El método más sencillo para ordenar es el de ascenso de
burbuja:

for i in 1..N-1 loop
for j in reverse i+1..N loop
if A(j) < A(j-1) then
intercambia(A(j),A(j-1));
end if;
end loop;
end loop;
La dependencia temporal del ascenso de burbuja es O(n2)

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

5

Notas:

UNIVERSIDAD DE CANTABRIA

Quizás el método de ordenación más sencillo es el de ordenación por ascenso de burbuja, que
se puede imaginar como un array vertical en el que se almacenan los registros a ordenar, y en el
que los registros de orden menor son más 'ligeros' que los de orden mayor y, por tanto, ascienden
flotando a las posiciones superiores del array.

Para implementar este algoritmo en el computador se realizan múltiples pasadas por el array de
abajo a arriba, analizando parejas de elementos contiguos, de modo que si su orden es incorrecto
se intercambian. Suponiendo que los elementos del array A son los registros a ordenar (del tipo
Elemento), en número N, el algoritmo se muestra en la transparencia anterior, donde el
procedimiento intercambia será:
procedure intercambia(x,y : in out Elemento) is
temp : Elemento:=x;
begin
x:=y;
y:=temp;
end intercambia;

Aunque este método es sencillo, su tiempo de ejecución es de tipo O(n2). Otros métodos sencillos,
como el de inserción o el de selección también presentan tiempos de este orden. Por tanto estos
métodos sencillos solamente son válidos cuando el número de elementos a ordenar es bajo.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

6

3.3 Ordenación rápida

UNIVERSIDAD DE CANTABRIA

El algoritmo de ordenación rápida (“quicksort”) es O(n log n)
en promedio (O(n2) en el peor caso):

El algoritmo es recursivo, y su pseudocódigo es:
procedimiento Quicksort(i,j,A) is
begin
if A(i)...A(j) posee, al menos, dos valores diferentes then
v:= pivote de A(i)...A(j);
-- el pivote de un conjunto de elementos es el mayor
-- de la primera pareja de elementos distintos
Particion de A(i..j);
-- Reordenar el array de forma que para
-- algún k entre i+1 y j A[i]...A[k-1] sean menores
-- que v, y A[k]...A[j] sean mayores o iguales que v
Quicksort(i,k-1);
Quicksort(k,j);
end if;
end Quicksort;

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

7

Notas:

UNIVERSIDAD DE CANTABRIA

Cuando es preciso ordenar listas de gran número de objetos es preciso recurrir a algoritmos más
rápidos, aunque también más complejos. Generalmente estos algoritmos presentan tiempos de
ejecución de tipo O(n⋅log n). El algoritmo “Quicksort” presenta tiempos de ejecución promedios de
tipo O(n⋅log n), pero en el peor caso pueden llegar a ser O(n2).

Este algoritmo permite ordenar un array A(1) ... A(n) tomando un valor del array, denominado
pivote, y organizando todos los elementos del array de forma que para un k dado todos los
elementos A(1) ... A(k-1) sean menores que el pivote y A(k) ... A(n) sean mayores o iguales.

Posteriormente se aplica el mismo procedimiento de forma recursiva a estos dos conjuntos de
elementos sucesivamente hasta que todo el array aparezca ordenado.

Puede observarse que este procedimiento será tanto más eficiente cuanto más se acerque el
elemento pivote al valor central de los elementos del array, para el que k=n/2.

Este algoritmo de ordenación rápida se puede expresar en pseudocódigo en la forma indicada en la
transparencia anterior. Su implementación se muestra en las transparencias siguientes.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

8

Implementación de
“Quicksort”

UNIVERSIDAD DE CANTABRIA

subtype Indice is Integer range 0..Max_Elem;
type Tipo_Elementos is array (Indice range 1..Max_Elem)
of Elemento;

procedure Ordenacion_Rapida (A : in out Tipo_Elementos;
N : in Indice) is
function Encuentra_Pivote
(i,j : in Indice; A : in Tipo_elementos) return Indice is
-- Devuelve 0 si todos los elementos son iguales.
begin
for k in i+1..j loop
if A(k)>A(i) then
return(k);
elsif A(k)<A(i) then
return(i);
end if;
end loop;
return(0); --no hay elementos diferentes
end Encuentra_Pivote;

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

9

Notas:

UNIVERSIDAD DE CANTABRIA

procedure Particion (i,j : in Indice;
Pivote : in Elemento;
A : in out Tipo_Elementos;
k : out Indice)
is
l : Indice:=i;
r : Indice:=j;
begin
loop
Intercambia(A(l),A(r));
while A(l) < Pivote loop
l:=l+1;
end loop;
while A(r) >= Pivote loop
r:=r-1;
end loop;
exit when l>r;
end loop;
k:=l;
end Particion;

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

10

Implementación de
“Quicksort” (cont.)

UNIVERSIDAD DE CANTABRIA

procedure Quicksort(i,j : in Indice;
A : in out Tipo_elementos) is
Pos_Pivote,k : Indice;
begin
Pos_Pivote:=Encuentra_Pivote(i,j,A);
if Pos_Pivote /= 0 then
Particion(i,j,A(Pos_Pivote),A,k);
Quicksort(i,k-1,A);
Quicksort(k,j,A);
end if;
end Quicksort;

begin -- Ordenacion_Rapida
Quicksort(1,N,A);
end Ordenacion_Rapida;

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

11

Notas:

UNIVERSIDAD DE CANTABRIA

Los tiempos de ejecución de este algoritmo son de O(n⋅log n) en el caso medio y de O(n2) en el
peor caso. Efectivamente, los tiempos de ejecución de peor caso para encuentra_pivote y
partición son de tipo O(j-i+1). En el peor caso el número de niveles de recursión es n (caso en el
que el pivote divide la lista en dos grupos uno de ellos de longitud 1) y, por tanto, el tiempo de peor
caso es O(n2).

En cambio en el caso medio, el número de niveles de recursión es proporcional a log n, por lo que
el tiempo de ejecución medio es O(n⋅log n).

Existen otros algoritmos que presentan tiempos de ejecución medios y de peor caso del orden de
O(n⋅log n). Sin embargo el tiempo de ejecución medio del algoritmo 'quicksort' es inferior, por un
factor constante, al de estos métodos.

Existen técnicas para mejorar el tiempo de ejecución de este algoritmo, basadas en realizar una
mejor elección del pivote. Por ejemplo, se pueden tomar tres elementos del array al azar y tomar
como pivote el de valor intermedio.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FAC