PDF de programación - Tema 4: Ordenación - Estructura de datos

Universidad de Valladolid
Departamento de informática

Campus de Segovia

Estructura de datos
Tema 4: Ordenación

Prof. Montserrat Serrano Montero

ÍNDICE

• Conceptos básicos
• Elección de un método
• Métodos directos
• Métodos indirectos

•

•

•

CONCEPTOS BÁSICOS

Ordenación de datos: operación consistente
en disponer una estructura de datos en una
colocación con respecto a uno de los campos
de elementos de un conjunto.
Clave: Elemento por el que está ordenado un
conjunto de datos.
Tipos de ordenación:
a) Según el orden:

Ascendentes: i < j ⇒ K [i] < = K [j]
Descendentes: i > j ⇒ K [i] > = K [j]

b) Según la cantidad de datos:

Directos: burbuja, selección, inserción
Indirectos (avanzados): rápida, mezcla
c) Según el lugar donde se almacenen los

datos:
interna: Si los datos están almacenados
en un array, una lista enlazada o un árbol.
(Memoria interna)
externa: Si los datos están almacenados
en un archivo. (Memoria secundaria).

•

•

•

•

ELECCIÓN DE UN MÉTODO

Según su eficiencia que mide la calidad y
rendimiento de un algoritmo.

Criterios:
a) El de menor tiempo de ejecución.
b) El de menor número de instrucciones.

Como no siempre se pueden efectuar estas
medidas, el mejor criterio es aislar una
operación específica del algoritmo y contar el
número de veces que se realiza.

En los algoritmos de ordenación, por ello, se
utiliza como medida de eficiencia el número
de comparaciones efectuadas entre los
elementos.

MÉTODOS DIRECTOS

ORDENACIÓN POR BURBUJA:

• Basada en comparar elementos adyacentes de la

lista e intercambiar sus valores si están
desordenados.

• Así se dice que los valores más pequeños

burbujean hacia el primer elemento de la lista,
mientras que los valores más grandes se hunden
hacia el final de la lista.

• Ej:

MÉTODOS DIRECTOS

ORDENACIÓN POR BURBUJA:
Pasada 1: i = 1

MÉTODOS DIRECTOS

ORDENACIÓN POR BURBUJA:

• Se necesitan 4 pasadas para ordenar una lista
de 5 elementos ⇒ n-1 pasadas para n elementos
- Pasada 1: 4 comparaciones y 3 intercambios
- Pasada 2: 3 comparaciones y 1 intercambio
- Pasada 3: 2 comparaciones y 1 intercambio
- Pasada 4: 1 comparaciones y 1 intercambio

• Algoritmo (pseudocódigo)
desde i ← 1 hasta n-1 hacer
desde j ← 1 hasta n-i hacer
si A[j] > A[j+1] entonces
Intercambio (A[j], A[j+1])

fin-si
fin-desde (bucle j)
fin-desde (bucle i)

MÉTODOS DIRECTOS

ORDENACIÓN POR BURBUJA:

type {en el programa principal}
Lista = array [1..n] of integer;
• Procedimiento:

procedure burbuja (var A: Lista; n: integer);
var i, j, aux: integer;
begin
for i:= 1 to n-1 do
for j:=1 to n-i do
if A[j] > A[j+1] then
begin {Intercambio dentro del programa}
aux:= A [j];
A[j] := A[j+1];
A[j+1] := aux
end;

end;

MÉTODOS DIRECTOS
ORDENACIÓN POR BURBUJA MEJORADO:

• Como esta técnica compara elementos consecutivos de una

lista, si en una pasada no ocurrieran intercambios,
significaría que la lista está ordenada.

• El algoritmo burbuja se puede mejorar si existe un

indicador que registre si se han producido intercambios en
la pasada. Si no se han producido cambios, la lista está
ordenada y se terminarán las comparaciones.

• Procedimiento:

procedure burbuja (var A: Lista; n: integer);
var i, j, aux: integer; NoIntercambio: boolean;
begin
i := 1;
repeat
NoIntercambio:= true;
for j:=1 to n-i do
if A[j] > A[j+1] then
begin {Intercambio dentro del programa}
aux:= A [j];
A[j] := A[j+1];
A[j+1] := aux;
NoIntercambio := false
end;
i := i + 1
until NoIntercambio = true
end;

MÉTODOS DIRECTOS

ORDENACIÓN POR SELECCIÓN:

• Consiste en escoger el elemento del array

(mayor/menor) y situarlo en uno de los
extremos del array, y el elemento que estaba en
esa posición intercambiarle por la posición del
elemento (mayor/menor).

• Pasos:

1. Encontrar el elemento mayor/menor de la
lista.
2. Intercambiar el elemento mayor con el
elemento de subíndice n (o bien si es el
elemento menor con el subíndice 1).
3. A continuación se busca el mayor en la
sublista de índices 1..n-1, y se intercambia con
el elemento subíndice n-1.
4. A continuación se busca el elemento mayor
de la sublista 1..n-2, y así sucesivamente.

MÉTODOS DIRECTOS
ORDENACIÓN POR SELECCIÓN: Ej

MÉTODOS DIRECTOS

ORDENACIÓN POR SELECCIÓN: Ej

• Se necesitan 4 pasadas para ordenar una lista de 5

elementos ⇒ n-1 pasadas para n elementos
- Pasada 1: 4 comparaciones y 1 intercambio
- Pasada 2: 3 comparaciones y 1 intercambio
- Pasada 3: 2 comparaciones y 1 intercambio
- Pasada 4: 1 comparaciones y 0 intercambios

• Algoritmo (pseudocódigo)

desde i ← n hasta 2 hacer

• Encontrar el elemento mayor del array 1..i
• Si el elemento mayor no está en el subíndice i,

entonces intercambiar elemento mayor con el de
subíndice j.

MÉTODOS DIRECTOS

ORDENACIÓN POR SELECCIÓN:

• Procedimiento:

function Mayor (ultimo: integer;A: Lista): integer;
var max, j: integer;
begin
max := 1;
for j:= 2 to ultimo do
if A[j] > A[max] then max := j;
Mayor := max
end;
procedure seleccion (var A: Lista; n: integer);
var i, j, aux: integer;
begin
for i:= n downto 2 do
begin
j := Mayor (i, A);
aux:= A [j];
A[j] := A[i];
A[i] := aux
end
end;

MÉTODOS DIRECTOS

ORDENACIÓN POR INSERCIÓN:

• El método se basa en considerar una parte de la

lista ya ordenada y situar cada uno de los
elementos restantes insertándolo en el lugar que
le corresponde por su valor, todos los valores a
la derecha se desplazan una posición para dejar
espacio.

• Ej:

MÉTODOS DIRECTOS
ORDENACIÓN POR INSERCIÓN: Ej

MÉTODOS DIRECTOS

ORDENACIÓN POR INSERCIÓN: Ej

• Se necesitan 4 pasadas para ordenar una lista
de 5 elementos ⇒ n-1 pasadas para n elementos

• Algoritmo (pseudocódigo)
desde i ← 2 hasta n hacer
• Guardar el valor de ese elemento en Aux
• Hacer espacio para Aux desplazando todos los

valores mayores que A[i] una posición

• Insertar el valor de Aux en el lugar del último

valor desplazado. fin-desde

MÉTODOS DIRECTOS

ORDENACIÓN POR INSERCIÓN:

• Procedimiento:
procedure Desplazar (var A: Lista; Aux, k: integer; var

NP: integer);
var Encontrado: boolean;
begin
while (k > 1) and not Encontrado do
if (A[k-1] > Aux) then
begin
A[k] := A[k-1];
k := k-1
end
else Encontrado := true;
NP := k
end;

procedure insercion (var A: Lista; n: integer);
var i, aux, NP: integer;
begin
for i:= 2 to n do
begin
Aux := A [i];
Desplazar (A, i, Aux, NP);
A[NP] := Aux

end
end;

COMPARACIÓN DE
MÉTODOS DIRECTOS

MÉTODOS INDIRECTOS

ORDENACIÓN RÁPIDA: (QUICKSORT)
Inventado por C.H. Hoare.

•

• Algoritmo recursivo que se rige por la estrategia

de “divide y vencerás”.

• Pasos:

1. Elegir un elemento del array ⇒ Pivote.
2. Dividir el array original en dos mitades, de
modo que en cada una de ellas estén los
elementos menores y mayores que el pivote.
3. Cada mitad debe estar ordenada. Para ello, se
procede como en los pasos 1 y 2 ⇒ Recursividad.
4. El proceso parará cuando las mitades estén
formadas por un solo elemento (ya está ordenado)

• La elección del pivote es arbitraria, aunque por
comodidad se suele utilizar el elemento central
del array, o bien el primero o el último elemento
del mismo.

MÉTODOS INDIRECTOS
ORDENACIÓN RÁPIDA: (QUICKSORT)
Elegimos el pivote, supongamos el término
central: Pivote = 21

1.

2. A continuación se establecen dos índices, uno
se inicializa a la posición primera del array y
otro a la última:

i = 1, j = 9

3. Mientras A[i] < Pivote se incrementa i y

mientras A[j] > Pivote se decrementa j.

4.

Se intercambian los elementos de las
posiciones i y j y se incrementa i y decrementa
j en una unidad.

MÉTODOS INDIRECTOS
ORDENACIÓN RÁPIDA: (QUICKSORT)
El proceso se repite

5.

6. Cuando j < i se ha terminado la partición. Se
han generado dos sublistas. La primera tiene
todos los elementos menores que 21 y la
segunda los mayores.

Sublista izquierda

Sublista derecha

7.

MÉTODOS INDIRECTOS
ORDENACIÓN RÁPIDA: (QUICKSORT)
La ordenación de las sublistas implica el
mismo proceso que antes, excepto que varían
los índices.
Sublista izquierda: (1, 5)

Sublista derecha: (6, 9)

MÉTODOS INDIRECTOS

ORDENACIÓN RÁPIDA: (QUICKSORT)
procedure rapido (var A: Lista; n: integer);
procedure partir (primero, ultimo: integer);
var i, j, central: integer;
procedure cambiar (var n, m: integer);
var aux: integer;
begin
aux := m; m := n; n := aux
end;
begin {partir}
i := primero; j := ultimo; central := A[(i + j) div 2];
repeat
while A [i] < central do i := i+1;
while A [j] > central do j := j-1;
if i <= j then
begin
cambiar (A[i], A[j]); i := i + 1; j := j – 1;
end
until i > j;
if primero < j then partir (primero, j);
if i < ultimo then partir (i, ultimo);

end; {partir}
begin {rapido}
partir (1, n)
end;

MÉTODOS INDIRECTOS

ORDENACIÓN POR MEZCLA: (MERGESORT)

• La idea básica de este algoritmo es la mezcla de

listas ya ordenadas.

• El proceso consiste en dividir la lista en dos
mitades y cada una de las mitades en otras
mitades, hasta que cada sublista contiene un
único elemento. (procedimiento recursivo).

• La mezcla comienza con las sublistas de un solo

elemento, que se mezclan en sublistas más
grandes cuyos elementos están ya ordenados, y el
proceso continúa hasta que se construye una
única lista ordenada.

• Pasos:

1. Dividir la lista en dos mitades.
2. Ordenar la sublista izquierda.
3. Ordenar la sublista derecha.
4. Mezclar las dos sublistas juntas.

MÉTODOS INDIRECTOS

ORDENACIÓN POR MEZCLA: (MERGESORT)

MÉTODOS INDIRECTOS
ORDENACIÓN POR MEZCLA: (MERGESORT)
procedure mezcla (var A: Lista; primero, ultimo: integer);
var central: integer;

procedure une (var L: Lista, izq, dcha, ptocent: integer);
var Aux: Lista; x, y,z: integer;
begin {une}
x := izq; y := ptocent; z := x
while (x < = ptocent) and (y <=dcha) do
{bucle para mezclar las sublistas}
begin
if L[x]<=L[y] then
begin

Aux [z] := L[x]; x:= x +1

end
else begin

Aux [z] := L[y];
y:= y +1

end;
z:=z+1
end; {while}
{bucles para copiar elementos restantes si existen}
while x <= ptocent do
begin
Aux [z]:= L[x]; x:=x+1;z:=z+1
end;

(Sigue...)

M